資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝學
法學在C++中查詢透過重新排列第二個陣列的元素可以形成的字典序最小的序列
假設我們有兩個包含n個數字的陣列A和B，我們必須在B自身中重新排列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
對於初始化i := 0，當i < n時，更新（i增加1），執行：
(my_map[b[i]]增加1)
將b[i]插入my_set
定義一個數組sequence
對於初始化i := 0，當i < n時，更新（i增加1），執行：
如果a[i]等於0，則：
it := my_set中不小於0的元素，最初指向第一個元素
value := it
在sequence的末尾插入value mod n
(my_map[value]減少1)
如果my_map[value]為零，則：
從my_set中刪除value
否則
x := n - a[i]
it := my_set中不小於x的元素，最初指向第一個元素
如果it不在my_set中，則：
it := my_set中不小於0的元素，最初指向第一個元素
value := it
在sequence的末尾插入(a[i] + value) mod n
(my_map[value]減少1)
如果my_map[value]為零，則：
從my_set中刪除value
返回sequence
示例
讓我們看看下面的實現，以便更好地理解：
#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, ]
更新於：2020年8月20日
380 次瀏覽
廣告