FilesExpand file tree

 master

/

FindTheDuplicateNumber287.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

67 lines (60 loc) · 1.79 KB

 master

/

FindTheDuplicateNumber287.java

Copy path

Top

File metadata and controls

• Code
• Blame

67 lines (60 loc) · 1.79 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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];

// }

}