查找可以通过重新排列C ++中第二个数组的元素而形成的按字典顺序排列的最小序列

假设我们有两个具有n个数字的数组A和B，我们必须以某种方式重新排列B的元素，以使在重新排列后由（A [i] + B [i]）％n形成的序列在字典上最小。最后，我们将返回字典上最小的序列。

因此，如果输入类似于A = {1,2,3,2}，B = {4,3,2,2}，那么输出将为[0，0，1，2]

为了解决这个问题，我们将遵循以下步骤-

• n：=一个的大小

• 定义一张映射my_map

• 定义一组my_set

• 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

• （将my_map [b [i]]增加1）

• 将b [i]插入my_set

• 定义数组序列

• 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

• ：= my_set中不小于0的元素，最初指向第一个元素

• 值：=它

• 在序列末尾插入值mod n

• （将my_map [value]减1）

• 如果my_map [value]为零，则-

• 从my_set中删除值

• 如果a [i]等于0，则-

• 除此以外

• 从my_set中删除值

• ：= my_set中不小于0的元素，最初指向第一个元素

• x：= n-a [i]

• ：= my_set中不小于x的元素，最初指向第一个元素

• 如果不在my_set中，则-

• 值：=它

• 在序列末尾插入（a [i] +值）mod n

• （将my_map [value]减1）

• 如果my_map [value]为零，则-

• 返回顺序

例 

让我们看下面的实现以更好地理解-

#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, ]