程序员面试金典 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处的值如果不正确，重复上述步骤即可。

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

最后

以上就是故意耳机为你收集整理的程序员面试金典 17.19的全部内容，希望文章能够帮你解决程序员面试金典 17.19所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。