Adcantage Shuffule
my solution
重要的是顺序, 如果有顺序, 可以节省很多性能. 即使需要排序, 也是可以接受的.
其次就是结果需要原始顺序, 那么可能就要需要一个值-索引的结构. 但是这可能复杂度太高了.
所以我选择排序, 但不生产值-索引的结构.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
vector<int> advantageCount(vector<int>& A, vector<int>& B) {
sort(A.begin(), A.end());
int b = 0;
vector<int> ret;
for (int i = 0; ; ++i) {
while (b < A.size() && A[b] <= B[i]) {
++b;
}
b = b == A.size() ? 0 : b;
ret.push_back(A[b]);
if (i + 1 >= B.size()) {
break;
}
A.erase(A.begin() + b);
if (B[i + 1] < B[i]) {
b = 0;
}
}
return std::move(ret);
}
};
|
虽然克预见的低效率, 但是代码整体很简洁, 达到了我想要的部分效果, 但是效率很低.
the best solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class Solution
{
public:
vector<int> advantageCount(const vector<int>& A, const vector<int>& B)
{
const int N = static_cast<int>(A.size());
vector<pair<int, int>> copyB(N);
for (int i = 0; i < N; ++i)
{
copyB[i] = {B[i], i};
}
sort(copyB.begin(), copyB.end(), [] (const pair<int, int>& lhs, const pair<int, int>& rhs) -> bool {
return lhs.first > rhs.first;
});
vector<int> copyA(A);
sort(copyA.begin(), copyA.end());
vector<int> ret(N);
int first = 0;
int last = N - 1;
for (const pair<int, int>& item : copyB)
{
if (copyA[last] > item.first)
{
ret[item.second] = copyA[last];
--last;
}
else
{
ret[item.second] = copyA[first];
++first;
}
}
return ret;
}
};
|
他的方法和我预料的差不多, 是两个顺序数组.
emm… 或许我有点过了? 我是想到值-索引的时候立马打断了这个想法. 因为觉得有点复杂了. 如果我继续想的话, 应该差不多就这个样子吧?