-
Notifications
You must be signed in to change notification settings - Fork 120
Expand file tree
/
Copy pathFindTheDuplicateNumber287.java
More file actions
67 lines (60 loc) · 1.79 KB
/
FindTheDuplicateNumber287.java
File metadata and controls
67 lines (60 loc) · 1.79 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/**
* 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.
*
* Example 1:
* Input: [1,3,4,2,2]
* Output: 2
*
* Example 2:
* Input: [3,1,3,4,2]
* Output: 3
*
* Note:
* You must not modify the array (assume the array is read only).
* You must use only constant, O(1) extra space.
* Your runtime complexity should be less than O(n2).
* There is only one duplicate number in the array, but it could be repeated
* more than once.
*/
public class FindTheDuplicateNumber287 {
public int findDuplicate(int[] nums) {
int low = 1, high = nums.length - 1;
while (low < high) {
int mid = (int) (low + (high - low) * 0.5);
int cnt = 0;
for (int a : nums) {
if (a <= mid) ++cnt;
}
if (cnt <= mid) low = mid + 1;
else high = mid;
}
return low;
}
public int findDuplicate2(int[] nums) {
int fast = nums[0];
int slow = nums[0];
while (true) {
// System.out.println("slow: " + slow + "; " + "fast: " + fast);
fast = nums[nums[fast]];
slow = nums[slow];
if (slow == fast) break;
}
fast = nums[0];
while (fast != slow) {
fast = nums[fast];
slow = nums[slow];
}
return slow;
}
// This modified the input array!
// public int findDuplicate(int[] nums) {
// int N = nums.length;
// Arrays.sort(nums);
// for (int i=0; i<N-1; i++) {
// if (nums[i] == nums[i+1]) return nums[i];
// }
// return nums[0];
// }
}