我的LeetCode：https://leetcode-cn.com/u/ituring/
我的LeetCode刷題原始碼[GitHub]：https://github.com/izhoujie/Algorithmcii
LeetCode 34. 在排序陣列中查找元素的第一個和最后一個位置
題目
給定一個按照升序排列的整數陣列 nums，和一個目標值 target，找出給定目標值在陣列中的開始位置和結束位置，
你的演算法時間復雜度必須是 \(O(log n)\) 級別，
如果陣列中不存在目標值，回傳 [-1, -1]，
示例 1:
輸入: nums = [5,7,7,8,8,10], target = 8
輸出: [3,4]
示例 2:
輸入: nums = [5,7,7,8,8,10], target = 6
輸出: [-1,-1]
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
解題思路
思路1-二分查找
一般二分查找只能確定一個位置，那么自然的會想到先確定target的最左位置然后while再確定最右位置；
但是這樣演算法就不是\(logn\)級別了，而是\(n\)級別，尤其當所有數都是target時，需要從頭到尾遍歷一遍；
所以應該對二分查找稍微調整下，呼叫兩次二分查找，一次找target的左邊界，一次找target的右邊界；
兩次的\(logn\)，最終仍為\(logn\)；
演算法復雜度:
- 時間復雜度： $ {\color{Magenta}{\Omicron\left(logn\right)}} $
- 空間復雜度： $ {\color{Magenta}{\Omicron\left(1\right)}} $
演算法原始碼示例
package leetcode;
/**
* @author ZhouJie
* @date 2020年1月19日 上午12:40:26
* @Description: 34. 在排序陣列中查找元素的第一個和最后一個位置
*
*/
public class LeetCode_0034 {
}
class Solution_0034 {
/**
* @author: ZhouJie
* @date: 2020年5月22日 下午9:01:09
* @param: @param nums
* @param: @param target
* @param: @return
* @return: int[]
* @Description: 1-兩次二分查找確定target的左右邊界；
*
*/
public int[] searchRange_1(int[] nums, int target) {
int[] rst = { -1, -1 };
int left;
// 左邊界定位
left = findBound(nums, target, true);
// 若left已越界或者最終定位的left不等于target，說明不存在target
if (left == nums.length || nums[left] != target) {
return rst;
}
rst[0] = left;
// 右邊界定位
rst[1] = findBound(nums, target, false) - 1;
return rst;
}
private int findBound(int[] nums, int target, boolean left) {
int l = 0, r = nums.length;
while (l < r) {
int m = (l + r) / 2;
// 關鍵點，left引數用來判斷是找左邊界還是找右邊界
if (nums[m] > target || (left && nums[m] == target)) {
r = m;
} else {
l = m + 1;
}
}
return l;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/185236.html
標籤：Java