[LeetCode] 287. Find the Duplicate Number

轉自LeetCode

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

1. You must not modify the array (assume the array is read only).
2. You must use only constant, O(1) extra space.
3. Your runtime complexity should be less than O(n2).
4. There is only one duplicate number in the array, but it could be repeated more than once.

<Solution>

這題是要在 array 裡面找到重複的數字

題意就像是，有13個人，一定有2個人的生日月份是重複的

解題想法如下

• 用生日月份來思考，12個月的中間是6月，歷遍一次整個 array，記算生日月份小於6月的有多少人

• 如果人數小於等於 6，那就代表重複的月份一定是在 7 到 12 月，也就是後半年

• 如果人數大於 6，就代表重複的月份一定是在 1 到 6 月，也就是前半年

• 重複以上 binary search，最後的 lower bound 就會是重複的那個月份

code 如下(參考資料)

	class Solution {
	public:
	int findDuplicate(vector<int>& nums) {
	int low = 1, high = nums.size() - 1;
	int mid, cnt;
	while(low < high) {
	mid = (low + high) / 2;
	cnt = 0;
	for(const auto &n : nums) {
	if(n <= mid) {
	++cnt;
	}
	}
	if(cnt <= mid) {
	//>> duplicate number is in [mid+1, high]
	low = mid+1;
	}
	else {
	//>> duplicate number is in [low, mid]
	high = mid;
	}
	}
	return low;
	}
	};

view raw findDuplicateNumberInArray_1.cpp hosted with ❤ by GitHub

這題還有一個很厲害的解法

用到的也是和 Link List Cycle  所使用的演算法 Floyd's Circle Detection Algorithm

因為已經確定 array 裡面有重複數字，可以視作這個 array 有一個迴圈

之前的想法是用指標往前的步數不同來思考

在這題，可以想成是函式對應關係

a = f(X)，b = f(X1)，c = f(X2) ...

如果有重複的數字，就代表存在 Xi != Xj，f(Xi) = f(Xj)

這邊，把 array[index] 當作函式，而在此 index 的值為 value

所以只要找到 array[index_1] = array[index_2]，就是找到迴圈了

然後快慢指針的部分，則可以用

slowIndex = array[slowIndex]

fastIndex = array[array[fastIndex]]

的方式來實現

那要找到重複的數字，其實就是 Link List Cycle II 所要求的迴圈起點

運用同樣的思考方式，把 slowIndex 移回到起始點，然後快慢指針每次都只往前一步

再次相遇的那個數字，就是重複的數字

code 如下(參考資料)

	class Solution {
	public:
	int findDuplicate(vector<int>& nums) {
	int slowIdx = 0, fastIdx = 0;
	//>> find the cycle
	while(true) {
	slowIdx = nums[slowIdx];
	fastIdx = nums[nums[fastIdx]];
	if(slowIdx == fastIdx) {
	break;
	}
	}
	//>> find the duplicate number
	slowIdx = 0;
	while(true) {
	slowIdx = nums[slowIdx];
	fastIdx = nums[fastIdx];
	if(slowIdx == fastIdx) {
	return fastIdx;
	}
	}
	}
	};

view raw findDuplicateNumberInArray_2.cpp hosted with ❤ by GitHub

還有一個更直覺的想法

因為題目限制，只會有一個數字重複，用一個set來檢查有沒有重複即可

Kotlin

	class Solution {
	fun findDuplicate(nums: IntArray): Int {
	val set = mutableSetOf<Int>()
	for(n in nums) {
	if(set.contains(n)) {
	return n
	}
	set.add(n)
	}
	return -1
	}
	}

view raw find_the_duplicate_number.kt hosted with ❤ by GitHub