-
Notifications
You must be signed in to change notification settings - Fork 26
/
Problem34_findFirstAndLastPositionOfElementInSortedArray.java
116 lines (99 loc) · 3.07 KB
/
Problem34_findFirstAndLastPositionOfElementInSortedArray.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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
package com.longluo.top100;
import java.util.Arrays;
/**
* 34. 在排序数组中查找元素的第一个和最后一个位置
* <p>
* 给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
* 如果数组中不存在目标值 target,返回 [-1, -1]。
* <p>
* 进阶:
* 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗?
* <p>
* 示例 1:
* 输入:nums = [5,7,7,8,8,10], target = 8
* 输出:[3,4]
* <p>
* 示例 2:
* 输入:nums = [5,7,7,8,8,10], target = 6
* 输出:[-1,-1]
* <p>
* 示例 3:
* 输入:nums = [], target = 0
* 输出:[-1,-1]
* <p>
* 提示:
* 0 <= nums.length <= 10^5
* -10^9 <= nums[i] <= 10^9
* nums 是一个非递减数组
* -10^9 <= target <= 10^9
* <p>
* https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
*/
public class Problem34_findFirstAndLastPositionOfElementInSortedArray {
// BF time: O(n) space: O(1)
public static int[] searchRange_bf(int[] nums, int target) {
int[] ans = {-1, -1};
int len = nums.length;
for (int i = 0; i < len; i++) {
if (nums[i] == target && ans[0] == -1) {
ans[0] = i;
} else if (nums[i] > target && ans[0] >= 0) {
ans[1] = i - 1;
return ans;
}
}
if (ans[0] >= 0) {
ans[1] = len - 1;
}
return ans;
}
// BS time: O(logn) space: O(1)
public static int[] searchRange_bs(int[] nums, int target) {
int[] ans = {-1, -1};
if (nums == null || nums.length <= 0) {
return ans;
}
ans[0] = binarySearchLeft(nums, target);
ans[1] = binarySearchRight(nums, target);
return ans;
}
public static int binarySearchLeft(int[] arr, int target) {
if (arr[arr.length - 1] < target) {
return -1;
}
int left = 0;
int right = arr.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return arr[left] == target ? left : -1;
}
public static int binarySearchRight(int[] arr, int target) {
if (arr[0] > target) {
return -1;
}
int left = 0;
int right = arr.length - 1;
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (arr[mid] > target) {
right = mid - 1;
} else {
left = mid;
}
}
return arr[left] == target ? left : -1;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(searchRange_bf(new int[]{2}, 2)));
searchRange_bf(new int[]{2, 2}, 2);
searchRange_bs(new int[]{2}, 2);
searchRange_bs(new int[]{2, 2}, 2);
searchRange_bs(new int[]{5, 7, 7, 8, 8, 10}, 8);
}
}