LeetCode 在排序元素中查找元素的第一個和最后一個位置

@TOC

題目描述

?給你一個按照非遞減順序排列的整數(shù)數(shù)組 nums，和一個目標值 target。請你找出給定目標值在數(shù)組中的開始位置和結束位置。

如果數(shù)組中不存在目標值 target，返回 [-1, -1]。

你必須設計并實現(xiàn)時間復雜度為 O(log n) 的算法解決此問題。

示例：

輸入：nums = [5,7,7,8,8,10], target = 8 輸出：[3,4]

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一個非遞減數(shù)組
-109 <= target <= 109

一、解題關鍵詞

非遞減
復雜度為O（logn）

二、解題報告

1.思路分析

1. 根據(jù)時間復雜度要求 可推斷 需要二分思想解決問題

2. 需要找到兩個坐標 left right ，分治思想，先找到一個坐標

3. Boolean flag 用來標識 用來區(qū)分左邊界尋找，還是右邊界尋找

2.時間復雜度

3.代碼示例

class Solution {
? ?//非遞減順序 遞增 或者相等
? ?public int[] searchRange(int[] nums, int target) {
? ? ? ?if (null == nums || nums.length < 1) return new int[]{-1, -1};
? ? ? ?int leftIdx = binarySearch(nums, target, true);
? ? ? ?int rightIdx = binarySearch(nums, target, false) - 1;
? ? ? ?if (leftIdx <= rightIdx
? ? ? ? ? ? ? ?&& rightIdx < nums.length
? ? ? ? ? ? ? ?&& nums[leftIdx] == target
? ? ? ? ? ? ? ?&& nums[rightIdx] == target) {
? ? ? ? ? ?return new int[]{leftIdx, rightIdx};
? ? ? ?}
? ? ? ?return new int[]{-1, -1};
? ?}

? ?int binarySearch(int[] nums, int target, Boolean flag) {
? ? ? ?int left = 0, right = nums.length - 1, ans = nums.length;
? ? ? ?while (left <= right) {
? ? ? ? ? ?int mid = left + (right - left) / 2;
? ? ? ? ? ?if (nums[mid] > target || (flag && nums[mid] >= target)) {
? ? ? ? ? ? ? ?right = mid - 1;
? ? ? ? ? ? ? ?ans = mid;
? ? ? ? ? ?} else {
? ? ? ? ? ? ? ?left = mid + 1;
? ? ? ? ? ?}

? ? ? ?}
? ? ? ?return ans;
? ?}
}

4.知識點

三、總結

1. 目的是為了找到一個區(qū)間 ==target

2. 找到左左邊后，要想辦法找到右坐標 且 左右坐標要有區(qū)別

3. 即，左邊坐標一定要讓right --

4. 右邊坐標 == target的時候 想辦法讓left ++

5. 兩個的區(qū)別就在于 mid >= target ? 大于 則右坐標-- 得到右邊界：左坐標++ 找到左邊界

6.