力扣刷题练习 七【34. 在排序数组中查找元素的第一个和最后一个位置】

前言

数组类型题目练习。
练习题 七【34. 在排序数组中查找元素的第一个和最后一个位置】

一、题目阅读

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

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

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

二、尝试实现

思路

• 理解题目：nums从小到大，已经排好顺序；第一个问题：找target在不在？第二个问题：返回target下标的开始和结束。
• 直观：用遍历nums一遍，但是时间复杂度O(n)。题目不让用。pass
• 找一个元素在不在集合里？可以想到哈希法。可是选择什么结构？用数组，还是要遍历nums，只是统计次数；用无序的unordered_set或者map，感觉都不好用，放次数还是放下标？还是得遍历nums，时间复杂度没降低。
• 二分查找：因为nums排好序，可以直接用。如果找到target，逐步缩小区间，就可以确定位置。nice。时间复杂度是O(log n)。

代码实现

测试通过。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> result;
        int left = 0;
        int right = nums.size()-1;
        while(left <= right){
            int middle = (left + right)/2;
            if(nums[middle] < target){
                left = middle + 1;
            }else if(nums[middle] > target){
                right = middle -1;
            }else if(nums[middle] == target){
                while(nums[left] < target){
                    left++;
                }
                while(nums[right] > target){
                    right--;
                }
                result.push_back(left);
                result.push_back(right);
                break;
            }
        }
        if(result.empty()){
            result = {-1,-1};
        }
        return result;
    }
};

三、参考答案

参考答案链接

学习内容

（1）左右边界分别来找，也是用二分法，可是在找边界的时候什么时候动left和right，有点绕还是。
（2）找右边界：

• 如果middle的值比target大，肯定在[left,middle-1]之间，所以只把right = middle-1;
• 若middle的值小于等于target，肯定在[middle+1,right]之间，所以left = middle+1;还要rightboard = left;
• 为什么rightboard在else条件下还要始终跟着left走？如果不走，会怎么样？最后直接return left？

（3）找左边界：

• 如果middle的值比target大，肯定在[left,middle-1]之间，所以只把right = middle-1;
• 若middle的值小于等于target，肯定在[middle+1,right]之间，所以left = middle+1;还要rightboard = left;
• 为什么leftboard在else条件下还要始终跟着right走？如果不走，会怎么样？最后直接return right？

总结

选择个人方法：使用二分查找，如果找到target，就逐步缩小两端。
参考思路：还需要去注意，找右边界是小于等于调整；找左边界是大于等于调整。不如个人方法。

（欢迎指正，转载标明出处）