題 目 ：找出數組中重復的數字。 在一個長度為n的數組里的所有數字都在0 ~ n-1的范圍內。數組中某些數字是重復的，但不知道有幾個數字重復了，也不知道每個數字重復了幾次。請找出數組中任意一個重復的數字。例如，如果輸入長度為7 的數組｛2,3, 1,0, 2, 5, 3｝ , 那么對應的輸出是重復的數字2 或者3。 先把輸入的數組排序。從排序的數組中找出重復的數字是一件很容易的事情，只需要從頭到尾掃描排序后的數組就可以了。排序一個長度為n的數組需要O(nlogn)的時間 還可以利用哈希表來解決這個問題。從頭到尾按順序掃描數組的每個數字，每掃描到一個數字的時候，都可以用0(1)的時間來判斷哈希表里是否已經包含了該數字。如果哈希表里還沒有這個數字，就把它加入哈希表。如果哈希表里已經存在該數字，就找到一個重復的數字。這個算法的時間復雜度是0(n)，但它提高時間效率是以一個大小為o(n)的哈希表為代價的。 我們再看看有沒有空間復雜度是0(1)的算法。如果這個數組中沒有重復的數字，那么當數組排序之后數字i將出現在下標為 i 的位置。由于數組中有重復的數字，有些位置可能存在多個數字，同時有些位置可能沒有數字。 現在讓我們重排這個數組。從頭到尾依次掃描這個數組中的每個數字。當掃描到下標為i的數字時，首先比較這個數字(用m表示)是不是等于i. 如果是，則接著掃描下一個數字；如果不是，則再拿它和第 m 個數字進行比較。如果它和第m個數字相等，就找到了一個重復的數字(該數字在下標為i和m 的位置都出現了)；如果它和第m個數字不相等，就把第i個數 字和第m個數字交換，把m 放到屬于它的位置。接下來再重復這個比較、 交換的過程，直到我們發現一個重復的數字 例子：數組{2,3,1,0,2,5,3};數組的第0個數字(從0開始計數)是2，與他的下標不匹配，因此將a[0]元素指定的坐標2互換，換完之后的結果是{1,3,2,0,2,5,3};這個時候0號元素是1，仍然和小標不匹配，繼續更換；更換之后的結果是{3,1,2,0,2,5,3};接下來繼續交換第0號元素和第3號元素，{0,1,2,3,2,5,3};0號元素、1號元素、2號元素、3號元素均匹配，當4號元素對應的數值是2和2號元素重復，因此找到了一個重復的數字 class Solution {
public : int findRepeatNumber ( vector< int > & nums) { int length = nums. size ( ) ; for ( int i = 0 ; i < length; i++ ) { while ( nums[ i] != i) { if ( nums[ i] == nums[ nums[ i] ] ) { return nums[ i] ; } else { int temp = nums[ i] ; nums[ i] = nums[ temp] ; nums[ temp] = temp; } } } return - 1 ; }
} ;
使用map，第一次遍歷元素，key是元素的本身數值，value是元素出現的次數，存儲所有的元素和出現次數的相關信息 第二次遍歷元素，查找元素出現的次數大于等于2的，返回對應的元素 int findRepeatNumber_3 ( std:: vector< int > & nums) { std:: map< int , int > map{ } ; int length = nums. size ( ) ; for ( int i = 0 ; i < length; ++ i) { map[ nums[ i] ] ++ ; } for ( auto i = map. cbegin ( ) ; i != map. cend ( ) ; ++ i) { if ( i- > second == 2 ) { return i- > first; } } return - 1 ; }
使用無需map，將元素加入map的時候就要判定，是不是之前已經存在了此元素，如果存在此元素，將其返回 int findRepeatNumber_2 ( std:: vector< int > & nums) { std:: unordered_map< int , int > map{ } ; int length = nums. size ( ) ; for ( int i = 0 ; i < length; ++ i) { if ( map. find ( nums[ i] ) != map. end ( ) ) { return nums[ i] ; } else { map[ nums[ i] ] ++ ; } } return - 1 ; }
將元素按照次序進行排序，然后判斷相鄰元素是否相等，如果相等則將其返回 
