數組中重復的數字

• 題目
• • 題目分析
• 題解
• • 方法一 哈希表
  • 方法二 暴力遍歷數組
  • 方法三 排序法
  • 方法四 利用數組下標和元素的特點新建數組
  • 方法五 數組原地交換

題目

找出數組中重復的數字。

在一個長度為 n 的數組 nums 里的所有數字都在 0～n-1 的范圍內。數組中某些數字是重復的，但不知道有幾個數字重復了，也不知道每個數字重復了幾次。請找出數組中任意一個重復的數字。在解答該題的時候大家可以根據自己對時間和空間的要求去選擇合適的算法。
示例 1：

輸入：
[2, 3, 1, 0, 2, 5, 3]
輸出：2 或 3

限制：

2 <= n <= 100000

題目分析

數組的長度為n且數組的元素內容為0到n-1，我們知道數組的下標就是從0開始到n-1,這個條件就讓我們對這個題目有了新的優化思路，具體見下文題解。
數組中重復的元素可能有很多，這里不要求找出全部的重復元素，只要找出的元素是其中之一即可，一般情況下找出的都是第一個出現的重復元素。

題解

方法一 哈希表

利用哈希表中元素不能重復的特點，我們先創建一個hashset然后將數組的元素依次添加進去，如果該元素在hashset中不存在，則添加成功，否則添加失敗說明數組中該元素已經存在，返回添加失敗的元素即為重復的第一個元素。

/*** 哈希表* 時間復雜度是 O(n)* 空間復雜度是 O(n)* @param nums* @return*/public static int findRepeatNumber(int[] nums) {Set<Integer> set = new HashSet<>();//hash表int res = -1;for (int num:nums){if (!set.add(num)){ //不允許重復元素添加，添加失敗返回0res = num;break;}}return res;}

由于for循環遍歷數組，時間復雜度為O(n)；
由于創建hash表需要申請額外的n個空間，空間復雜度為O(n);

方法二 暴力遍歷數組

直接使用數組的遍歷，遍歷數組中的每一個元素，然后在剩下的元素中尋找是否存在相同的元素，如果存在直接返回。如果遍歷完數組還沒有找到重復的元素則表示數組中不存在重復元素，返回-1。

*** 暴力求解* 時間復雜度是 O(n^2)* 空間復雜度是 O(1)* @param nums* @return*/public int findRepeatNumber(int[] nums) {for (int i = 0; i < nums.length; i++) {for (int j = i + 1; j < nums.length; j++) {if (nums[i] == nums[j]) {return nums[i];}}}return -1;}

方法三 排序法

因為數組中的元素是在0~數組長度-1，所以可以將數組的元素進行排序，排序后的數組中重復元素是相鄰的，通過判斷一個元素的相鄰元素是否和它相同在查找重復元素。

public int findRepeatNumber5(int[] nums) {// 排序后的數組，重復元素必然相鄰Arrays.sort(nums);int res = 0;for(int i = 0; i < nums.length - 1; i++){// 找到重復元素if(nums[i] == nums[i+1]){res = nums[i];break;}}return res;}

這里Arrays.sort()方法的時間復雜度具有不確定性，當數組中元素個數小于286且小于47進行插入排序，元素個數小于286但是大于47的進行快速排序；元素個數大于286且數組不具備結構的按照小于286的進行看待，元素個數大于286且數組具備結構的進行歸并排序，每種排序的時間復雜度都不一樣。
對于Arrays.sort()方法的底層原理大家不了解的話可以看
這篇文章

方法四 利用數組下標和元素的特點新建數組

數組長度為n，利用數組下標和數組元素都是從0~n-1，我們可以將數組的元素當作下標使用，新建一個全是-1的數組，然后遍歷原來的數組，將數組的元素作為下標，數組的下標作為值存入新數組中，一個下標被訪問一次的元素只出現一次，一個下標被多次訪問的元素就是重復出現的元素。（新數組初始化為全是-1是因為原數組的元素都是0 ~n-1,便于后續訪問的時候判斷是否訪問過 ）

public int findRepeatNumber(int[] nums) {int[] res = new int[nums.length];Arrays.fill(res, -1);for (int i = 0; i < nums.length; i++) {// 2. 判斷當前元素是否已經存在if (res[nums[i]] != -1) {// 如果存在，則直接返回return nums[i];} ?// 否則的話，將當前元素作為索引，當前元素的下標作為值，填入新建的數組中，如果新建數組中該位置是-1，說明當前元素是第一次出現；如果新建數組中該位置已經被其他數字填充了，說明當前元素重復出現res[nums[i]] = i;}return -1; }

時間復雜度是 O(n)
空間復雜度是 O(n)
在這里使用數組比使用哈希表能更節省空間，且使用數組的性能更高。哈希表底層使用的是數組加鏈表還有紅黑樹，它的數組一般都是用不滿的就存在浪費空間。而且哈希表中查找的時候要進行哈希計算，有可能出現沖突。

方法五 數組原地交換

利用方法四的思想，但是方法四中新建的數組增加了空間復雜度，其實我們不新建數組也可以使用該思想完成。

public static int findRepeatNumber4(int[] nums) {for (int i = 0 ;i < nums.length;i++){while (i!=nums[i]){if (nums[nums[i]] == nums[i]){return nums[i];} // int temp = nums[i]; // nums[i] = nums[nums[i]]; // nums[nums[i]] = temp;// 交換int tmp = nums[nums[i]];nums[nums[i]] = nums[i];nums[i] = tmp;}}return -1;}

時間復雜度是 O(n)
空間復雜度是 O(1)
注意：使用該方法的時候需要注意，交換nums[i]和nums[nums[i]]的時候不能先進行nums[i] = nums[nums[i]]，這樣的話nums[i]改變了nums[nums[i]]也隨之改變。
以下是我畫圖的一個分析(有點丑大家表介意)：

總結

以上是生活随笔為你收集整理的剑指offer03-数组中重复的数字(java)|leetcode刷题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。