?LeetCode刷題實(shí)戰(zhàn)34：在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置
算法的重要性，我就不多說(shuō)了吧，想去大廠，就必須要經(jīng)過(guò)基礎(chǔ)知識(shí)和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號(hào)后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！
今天和大家聊的問(wèn)題叫做在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置，我們先來(lái)看題面：
https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
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].
題意
樣例
示例 1:
輸入: nums = [5,7,7,8,8,10], target = 8
輸出: [3,4]
示例?2:
輸入: nums = [5,7,7,8,8,10], target = 6
輸出: [-1,-1]
題解
target的,但是找到的target不知道是最左邊的數(shù)還是最右邊的數(shù),所以,通過(guò)找到這個(gè)數(shù)再找出相應(yīng)的邊界值.target在最左邊的位置,在求出另一個(gè)邊界!https://www.zhihu.com/question/36132386/answer/530313852),讀完之后,可以加深二分搜索的理解!
class?Solution?{
????public?int[] searchRange(int[] nums, int?target) {
????????int[] res = {-1, -1};
????????int?n = nums.length;
????????if?(n == 0) return?res;
????????int?left = 0;
????????int?right = n-1;
????????while?(left <= right){
????????????int?mid = left + (right - left) / 2;
????????????if?(nums[mid] == target) {
????????????????left = mid;
????????????????right = mid;
????????????????while?(left > 0?&& nums[left] == nums[left-1]) left--;
????????????????while?(right < n - 1?&& nums[right] == nums[right+1]) right++;
????????????????res[0] = left;
????????????????res[1] = right;
????????????????return?res;
????????????}
????????????else?if?(nums[mid] > target) right = mid - 1;
????????????else?left = mid + 1;
????????}
????????return?res;
????????
????}
}
bisect.bisect_left(a,x,lo=0,hi=len(a))在a中找x最左邊數(shù)的索引,如果找不到就返回插入的索引.上期推文：