题解 | #数组中重复的数字#
数组中重复的数字
https://www.nowcoder.com/practice/6fe361ede7e54db1b84adc81d09d8524
#include <fstream> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param numbers int整型vector * @return int整型 */ int duplicate(vector<int>& numbers) { // write code here for(int i=0;i<numbers.size();i++){ if(numbers.size()==0){ return -1; } while(numbers[i]!=i){ if (numbers[i]==numbers[numbers[i]]) { return numbers[i]; } swap(numbers[i], numbers[numbers[i]]); } } return -1; } };
按照顺序将数组中每个值都交换到与值对应下标的位置,交换swap的目的是保存目标位置的值,并且不另外占用存储空间,数组中的每个值仅需进行一次交换,故时间复杂度为O(n),除了索引和swap之外没有额外占用栈空间,因此空间复杂度为O(1)。
此外,看到有一个解法是建立一个集合set,把数组中的值一个个丢进去,判断set中是否已经存在同样的值,这样做的时间复杂度其实是O(nlogn), 因为set的搜索的时间复杂度为O(logn)。