查找可以通过重新排列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, ]

      以上是 查找可以通过重新排列C ++中第二个数组的元素而形成的按字典顺序排列的最小序列 的全部内容, 来源链接: utcz.com/z/316309.html

      回到顶部