未分類

Find the Duplicate Number

Array, BinarySearch, Go, LeetCode, TwoPointers

Find the Duplicate Number

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.
提示 解題應用
BinarySearch BinarySearch

Default:

1
2
3
func findDuplicate(nums []int) int {
}

解答思路:

有一長度為n+1的陣列包含了1~n的值，只會有同一個數字重覆，不會有多個數字重覆的情況，其中至少會出現一個重覆值(也可能更多)，要在空間複雜度為O(1)與時間複雜度為O(n^2)內找出該個重覆的數字，且不能藉由修改陣列內容來節省空間與時間，這麼一來肯定無法使用像是排序或HashMap等手段，只好先取出1~n的中間值，接著統計整個陣列的所有元素，看大多數的元素是比中間值大還是比中間值小，如果大多數比中間值小表示重覆的元素是落在1~中間值之間，而如果大多數比中間值大表示重覆的元素是落在中間值~n之間，最後不斷重覆上述的二分法便能找出重覆的元素是哪一個數字。

程式碼解說:

如思路所述因為每次都要從範圍1~n中取出中間值，所以一開始定義開頭為1，結尾為n(陣列長度為n+1所以需將其減1)，之後不斷將兩者相加除以2取得中間值，接著統計整個陣列的所有元素，取出的元素小於等於中間值的話(落在1~中間值之間)將計數器+1，統計完後如果計數器小於等於中間值，表示重覆的元素都落在後頭(中間值+1~n)，此時就把中間值+1做為新範圍的開頭，反之如果計數器大於中間值，表示重覆的元素都落在前面(1~中間值)，就把中間值做為新範圍的結尾，最後不斷重覆上述的二分法直到開頭與結尾值相等為止，便能找出重覆的元素是哪一個數字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var mid int
var count int
front := 1
rear := len(nums) - 1
for front < rear {
	mid = (front + rear) / 2
	count = 0
	for _, v := range nums {
		if v <= mid {
			count++
		}
	}
	if count <= mid {
		front = mid + 1
	} else {
		rear = mid
	}
}
return front

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func findDuplicate(nums []int) int {
	var mid int
	var count int
	front := 1
	rear := len(nums) - 1
	for front < rear {
		mid = (front + rear) / 2
		count = 0
		for _, v := range nums {
			if v <= mid {
				count++
			}
		}
		if count <= mid {
			front = mid + 1
		} else {
			rear = mid
		}
	}
	return front
}

總結:

有一長度為n+1的陣列包含了1~n的值，只會有同一個數字重覆並需要將其找出，其中至少會出現一個重覆值(也可能更多)，要在空間複雜度為O(1)與時間複雜度為O(n^2)內找出該個重覆的數字，且不能藉由修改陣列內容來節省空間與時間，只好先取出1~n的中間值，接著統計整個陣列的所有元素，看大多數的元素是比中間值大還是比中間值小，如果大多數比中間值小表示重覆的元素是落在1~中間值之間，而如果大多數比中間值大表示重覆的元素是落在中間值~n之間，最後不斷重覆上述的二分法便能找出重覆的元素是哪一個數字。

分享到