我的LeetCode：https://leetcode-cn.com/u/ituring/

我的LeetCode刷題源碼[GitHub]：https://github.com/izhoujie/Algorithmcii

LeetCode 面試題03. 數組中重覆的數字

題目

找出數組中重覆的數字。

在一個長度為 n 的數組 nums 里的所有數字都在 0～n-1 的範圍內。數組中某些數字是重覆的，但不知道有幾個數字重覆了，也不知道每個數字重覆了幾次。請找出數組中任意一個重覆的數字。

示例 1：

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

限制：

• 2 <= n <= 100000

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof
著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。

解題思路

• 鴿巢計數，創建用於保存n個數的長度為n的數組；
• 原地校驗，即校驗i和[i]是否相等，不相等則把[i]放到i的位置上；

思路1-鴿巢計數

略

演算法複雜度:

• 時間複雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
• 空間複雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $

思路2-原地值與索引的校驗

略
演算法複雜度:

• 時間複雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
• 空間複雜度： $ {\color{Magenta}{\Omicron\left(1\right)}} $

演算法源碼示例

package leetcode;

/**
 * @author ZhouJie
 * @date 2020年4月28日 下午4:10:35 
 * @Description: 面試題03. 數組中重覆的數字
 *
 */
public class LeetCode_Offer_03 {
	/**
	 * @author: ZhouJie
	 * @date: 2020年4月28日 下午4:28:09 
	 * @param: @param nums
	 * @param: @return
	 * @return: int
	 * @Description: 1-統計
	 *
	 */
	public int findRepeatNumber_1(int[] nums) {
		int[] stastic = new int[nums.length];
		for (int i : nums) {
			stastic[i]++;
			if (stastic[i] > 1) {
				return i;
			}
		}
		return nums[0];
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年4月28日 下午4:28:24 
	 * @param: @param nums
	 * @param: @return
	 * @return: int
	 * @Description: 2-歸位校驗
	 *
	 */
	public int findRepeatNumber_2(int[] nums) {
		for (int i = 0; i < nums.length; i++) {
			while (nums[i] != i) {
				if (nums[nums[i]] == nums[i]) {
					return nums[i];
				}
				nums[i] = nums[i] ^ nums[nums[i]];
				nums[nums[i]] = nums[i] ^ nums[nums[i]];
				nums[i] = nums[i] ^ nums[nums[i]];
			}
		}
		return -1;
	}

}