C++에서 두 번째 배열의 요소를 재배열하여 형성할 수 있는 사전순으로 가장 작은 시퀀스 찾기

n개의 숫자를 가진 두 개의 배열 A와 B가 있다고 가정하면 (A[i] + B[ i]) % n 재정렬 후 사전순으로 가장 작습니다. 마지막으로 사전순으로 가능한 가장 작은 시퀀스를 반환합니다.

따라서 입력이 A ={1, 2, 3, 2}, B ={4, 3, 2, 2}인 경우 출력은 [0, 0, 1, 2]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• n :=a

  의 크기

• 하나의 지도 my_map 정의

• 한 세트 my_set

  정의

• initialize i :=0의 경우, i

  • (my_map[b[i]] 1 증가)

  • b[i]를 my_set

    에 삽입

• 배열 시퀀스 정의

• initialize i :=0의 경우, i

  • a[i]가 0과 같으면 -

    • it :=0보다 작지 않은 my_set의 요소, 처음에는 첫 번째 요소를 가리킵니다.

    • 가치 :=그것

    • 시퀀스 끝에 값 mod n 삽입

    • (my_map[값]을 1만큼 감소)

    • my_map[값]이 0이면 -

      • my_set에서 값 삭제

• 그렇지 않으면

  • x :=n - a[i]

  • it :=x보다 작지 않은 my_set의 요소, 처음에는 첫 번째 요소를 가리킵니다.

  • my_set에 없으면 -

    • it :=0보다 작지 않은 my_set의 요소, 처음에는 첫 번째 요소를 가리킵니다.

  • 가치 :=그것

  • 시퀀스 끝에 (a[i] + 값) mod n 삽입

  • (my_map[값]을 1만큼 감소)

  • my_map[값]이 0이면 -

    • my_set에서 값 삭제

• 반환 순서

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v) {
   cout << "[";
   for (int i = 0; i < v.size(); i++) {
      cout << v[i] << ", ";
   }
   cout << "]" <; endl;
}
vector<int> solve(vector<int>&a, vector<int> &b) {
   int n = a.size();
   unordered_map<int, int> my_map;
   set<int> my_set;
   for (int i = 0; i < n; i++) {
      my_map[b[i]]++;
      my_set.insert(b[i]);
   }
   vector<int> sequence;
   for (int i = 0; i < n; i++) {
      if (a[i] == 0) {
         auto it = my_set.lower_bound(0);
         int value = *it;
         sequence.push_back(value % n);
         my_map[value]--;
         if (!my_map[value])
            my_set.erase(value);
         }
         else {
            int x = n - a[i];
            auto it = my_set.lower_bound(x);
            if (it == my_set.end())
               it = my_set.lower_bound(0);
            int value = *it;
            sequence.push_back((a[i] + value) % n);
            my_map[value]--;
            if (!my_map[value])
               my_set.erase(value);
         }
      }
   return sequence;
}
int main() {
   vector<int> a = {1, 2, 3, 2};
   vector<int> b = {4, 3, 2, 2};
   vector<int> res = solve(a, b);
   print_vector(res);
}

입력

{1, 2, 3, 2}, {4, 3, 2, 2}

출력

[0, 0, 1, 2, ]