LeetCode 442 题目解答:意思就是给一个长度为 n 的数组,数组中的元素大小在 [1,n] 之间, 数组中的元素可能会重复出现两次,或者出现一次,或者不出现,找出所有重复出现两次的元素。
这一题和 LeetCode 的 448 题 Find All Numbers Disappeared in an Array 的思想是类似的,我在做 Find All Numbers Disappeared in an Array 这题时,用的是很一般的做法,在关于 448 题的讨论中,我看到了另一种时间复杂度为 O(n),空间复杂度为 O(1) 的做法,并把它记录在了 448 题的博客中,根据这种思想,这题的时间复杂度为 O(n),空间复杂度为 O(1) 的代码如下:
- class Solution {
- public: vector findDuplicates(vector & nums) {
- vector ans; //存储结果 for(int i=0;i0){ nums[m]=-nums[m]; } else if(nums[m]<0){ ans.push_back(m+1); } } return ans; }};
用时 142ms,击败了 60.12% 的 c++ 程序。
思想就是遍历数组一遍,在遍历的过程中,令 m=abs(nums[i])-1,减一是为了让下标从 0 开始,如果 nums[m] 为正,就将 nums[m]=-nums[m],说明 m+1 出现了一次;如果 nums[m] 为负,这说明 m+1 已经出现了一次,这次是第二次出现,所以将 m+1 放入 ans 中。
就爱阅读 www.92to.com 网友整理上传, 为您提供最全的知识大全, 期待您的分享,转载请注明出处。
来源: http://www.92to.com/bangong/2017/02-25/17598218.html