程序员面试金典 17.19

71 阅读 0 评论 47 点赞

我是靠谱客的博主故意耳机，这篇文章主要介绍程序员面试金典 17.19，现在分享给大家，希望可以做个参考。

Missing Two：在含有n - 2个元素的非重复数组中，只包含[1, n]之间的值，在O(n)的时间和O(1)的空间复杂度下找出缺失的两个值。

这应该是《编程之美》上的进阶题，可以通过找两个等式，然后解二元方程算出答案，不过好像有点复杂的样子。

看了一下题解有了思路。如果数组是有序的，那么遍历一下就能找到缺失的元素了，所以要解决如何排序。因为题设保证了在有序时，num[i] == i + 1，所以可以把位置nums[i] - 1处的值和位置i处的值nums[i]交换，这样位置nums[i] - 1上的值就是排序后的值nums[i]，而位置i处的值如果不正确，重复上述步骤即可。

复制代码

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
class Solution {
private:
void swap(int &a, int &b)
{
int t = a;
a = b;
b = t;
}
public:
vector<int> missingTwo(vector<int>& nums) {
nums.push_back(0);
nums.push_back(0);
for(int i = 0; i < static_cast<int>(nums.size()); i++)
{
while(nums[i] != 0 && nums[i] != i + 1){
swap(nums[i], nums[nums[i] - 1]);
}
}
vector<int> ret;
for(int i = 0; i < static_cast<int>(nums.size()); i++)
{
if(nums[i] == 0) ret.push_back(i + 1);
}
return ret;
}
};