-
Notifications
You must be signed in to change notification settings - Fork 4
Expand file tree
/
Copy pathLeetCode34.java
More file actions
150 lines (135 loc) · 4.76 KB
/
Copy pathLeetCode34.java
File metadata and controls
150 lines (135 loc) · 4.76 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
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
package LeetCode.array;
import java.util.Arrays;
/**
* Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
*/
public class LeetCode34 {
public int[] searchRange(int[] nums, int target) {
int[] result = {-1, -1};
if (nums == null || nums.length == 0) return result;
int divide = binary(nums, 0, nums.length-1, target);
if(divide < 0) return result;
result[0] = divide;
if(divide > 0) {
int start = lastLeft(nums, divide, target);
if (start >= 0) result[0] = start;
}
if(divide == nums.length-1) result[1] = divide;
else {
int end = lastRight(nums, divide, target);
if(end < 0) result[1] = divide;
else result[1] = end;
}
return result;
}
//二分
private int binary(int[] nums, int lo, int hi, int target){
while(lo <= hi){
int mid = lo + (hi-lo)/2;
if(nums[mid] < target) lo = mid + 1;
else if(nums[mid] > target) hi = mid - 1;
else return mid;
}
return -1;
}
//循环找到最左点
private int lastLeft(int[] nums, int index, int target){
int preIndex = -1;
while(index > 0){
preIndex = index;
index = binary(nums, 0, index-1, target);
if(index == 0){
return index;
}
}
return preIndex;
}
//循环找到最右
private int lastRight(int[] nums, int index, int target){
int preIndex = -1;
index = binary(nums, index+1, nums.length-1, target); //index可能为0
while(index > 0){
preIndex = index;
index = binary(nums, index+1, nums.length-1, target);
if(index == nums.length-1){
return index;
}
}
return preIndex;
}
//====================================================
//方法二
public int[] search(int[] nums, int target){
if(nums == null || nums.length == 0) return new int[]{-1,-1};
return new int[]{searchLeft(nums, target), searchRight(nums, target)};
}
private int searchLeft(int[] nums, int target){
int start = 0, end = nums.length-1;
while (start + 1 < end){ //长度大于2，进行查找；循环到start+1=end停止
int mid = start + (end-start)/2;
if(nums[mid] >= target){
end = mid;
}else {
start = mid; //由于循环的条件这里不能写成start = mid+1；
}
}
if(nums[start] == target){ //这里先判断start，因为nums[0]可能等于target, 其他情况nums[start] != target
return start;
}else if(nums[end] == target){
return end;
}else {
return -1;
}
}
private int searchRight(int[] nums, int target){
int start = 0, end = nums.length-1;
while(start + 1 < end){
int mid = start+(end-start)/2;
if(nums[mid] <= target){
start = mid;
}else {
end = mid;
}
}
if(nums[end] == target){ //这里先判断end，因为nums[nums.length-1]可能等于target，其他情况nums[end] != target
return end;
}else if(nums[start] == target){
return start;
}else {
return -1;
}
}
// 优化代码
public int[] searchRange2(int[] nums, int target) {
int[] res = {-1, -1};
if(nums == null || nums.length == 0) return res;
int l = 0, h = nums.length-1;
while(l < h) {
int mid = l+(h-l)/2;
if(nums[mid] >= target) h = mid;
else l = mid+1;
}
if(nums[h] == target) res[0] = h;
l = h;
h = nums.length-1;
while(l < h) {
int mid = l+(h-l)/2+1;
if(nums[mid] > target) h = mid-1;
else l = mid;
}
if(nums[l] == target) res[1] = l;
return res;
}
public static void main(String[] args) {
LeetCode34 test = new LeetCode34();
int[] nums = {5,7,7,4,6,8,8,10};
int[] result = test.search(nums, 8);
System.out.println(Arrays.toString(result));
result = test.search(nums, 6);
System.out.println(Arrays.toString(result));
result = test.search(nums, 10);
System.out.println(Arrays.toString(result));
}
}