Tìm dãy nhỏ nhất về mặt từ vựng có thể được hình thành bằng cách sắp xếp lại các phần tử của mảng thứ hai trong C ++

Giả sử chúng ta có hai mảng A và B với n số, chúng ta phải sắp xếp lại các phần tử của B theo cách sao cho dãy được tạo bởi (A [i] + B [ i])% n sau khi sắp xếp lại nó là nhỏ nhất về mặt từ vựng. Cuối cùng, chúng tôi sẽ trả về trình tự nhỏ nhất có thể về mặt từ vựng.

Vì vậy, nếu đầu vào là A ={1, 2, 3, 2}, B ={4, 3, 2, 2}, thì đầu ra sẽ là [0, 0, 1, 2]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của một

• Xác định một bản đồ my_map

• Xác định một tập hợp my_set

• để khởi tạo i:=0, khi i

  • (tăng my_map [b [i]] lên 1)

  • chèn b [i] vào my_set

• Xác định một chuỗi mảng

• để khởi tạo i:=0, khi i

  • nếu [i] giống 0, thì -

    • it:=các phần tử của my_set không nhỏ hơn 0, ban đầu trỏ đến phần tử đầu tiên

    • value:=it

    • chèn giá trị mod n vào cuối chuỗi

    • (giảm my_map [value] xuống 1)

    • nếu my_map [value] bằng 0, thì -

      • xóa giá trị khỏi my_set

• Nếu không

  • x:=n - a [i]

  • it:=các phần tử của my_set không nhỏ hơn x, ban đầu trỏ đến phần tử đầu tiên

  • nếu nó không có trong my_set, thì -

    • it:=các phần tử của my_set không nhỏ hơn 0, ban đầu trỏ đến phần tử đầu tiên

  • value:=it

  • insert (a [i] + value) mod n vào cuối chuỗi

  • (giảm my_map [value] xuống 1)

  • nếu my_map [value] bằng 0, thì -

    • xóa giá trị khỏi my_set

• trình tự trả về

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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);
}

Đầu vào

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

Đầu ra

[0, 0, 1, 2, ]