-
Notifications
You must be signed in to change notification settings - Fork 147
/
Duplicate51.java
94 lines (87 loc) · 2.3 KB
/
Duplicate51.java
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
package com.so;
import java.util.HashSet;
/**
* 第51题
* 在一个长度为n的数组里的所有数字都在0到n-1的范围内,找出数组中任意一个重复的数字
*
* @author qgl
* @date 2017/08/29
*/
public class Duplicate51 {
/**
* 解法一:利用题中数组的特点(数组中的元素小于数组长度)
* 时间复杂度是O(n),空间复杂度是O(1)
*
* @param numbers
* @return
*/
public static Integer duplicate1(int numbers[]) {
if (numbers == null || numbers.length == 0) {
return null;
}
if (numbers.length == 1) {
return numbers[0];
}
int length = numbers.length;
for (int i = 0; i < length; i++) {
int index = numbers[i];
if (index >= length) {
index -= length;
}
if (numbers[index] >= length) {
return index;
}
numbers[index] += length;
}
return null;
}
/**
* 解法二:利用辅助空间 HashSet
* 时间复杂度是O(n),空间复杂度是O(n)
*
* @param numbers
* @return
*/
public static Integer duplicate2(int numbers[]) {
if (numbers == null || numbers.length == 0) {
return null;
}
if (numbers.length == 1) {
return numbers[0];
}
int length = numbers.length;
HashSet<Integer> hashSet = new HashSet<>();
for (int i = 0; i < length; i++) {
if (!hashSet.add(numbers[i])) {
return numbers[i];
}
}
return null;
}
/**
* 解法三:快慢指针
*
* @param numbers
* @return
*/
public static int duplicate3(int[] numbers) {
if (numbers == null || numbers.length == 0) {
return -1;
}
int slow = 0;
int fast = 0;
for (int i = 0; i < numbers.length; i++) {
slow = numbers[slow];
fast = numbers[numbers[fast]];
if (fast == slow) {
fast = 0;
while (fast != slow) {
fast = numbers[fast];
slow = numbers[slow];
}
return slow;
}
}
return -1;
}
}