锐客网

  1. 首页 > 睿知 > it技术 > >

算法 Find All Numbers Disappeared in an Array

IT知识numbersnumber

大鹏一日同风起，扶摇直上九万里。这篇文章主要讲述算法 Find All Numbers Disappeared in an Array相关的知识，希望能为你提供帮助。
题目：整数数组满足1< =a[i]< =n(ｎ是数组的长度），某些元素出现一次，某些元素出现两次，在数组a[i]中找到【１，ｎ】区间中未出现的数字。比如输入【４，３，２，７，８，２，３，１】，输出【５，６】。时间复杂度要求是Ｏ（ｎ)，空间复杂度要求Ｏ(1)
思路：看许多网友说用ｓｅｔ数据结构去做，这就违反了空间复杂度的要求，所以排序还是要本地做的。遍历数组，把这个数字放到它该待的地方：比如a[0]=4，那么我们就把４放到a[3]处，然后把a[3]处的７放到a[6]处，把a[6]处３放在a[2]处，把a[2]处的２放在a[1]处，晕了吧
这样做：
ｓｔｅｐ１: ７，３，２，４，８，２，３，１
ｓｔｅｐ２：３，３，２，４，８，２，７，１
ｓｔｅｐ３：２，３，３，４，８，２，７，１
ｓｔｅｐ４：３，２，３，４，８，２，７，１
ｓｔｅｐ４．１：此时想着交换３和３，但是发现重了，那么３还是待在原位吧，
ｓｔｅｐ５：
答案：
https://github.com/honpey/codebox/blob/master/leetcode/array/p448.cpp
相关：
对于数组１< =a[i]< =n，
【算法 Find All Numbers Disappeared in an Array】 

    推荐阅读


    上一篇：怎么使用chrome调试andriod app（Hybrid App）

    下一篇：Android双系统实现