首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【每日一题】34. Find First and Last Position of Element in Sorted Array

【每日一题】34. Find First and Last Position of Element in Sorted Array

作者头像
公众号-不为谁写的歌
发布2020-08-11 15:13:39
2380
发布2020-08-11 15:13:39
举报
文章被收录于专栏:桃花源记桃花源记

题目描述

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].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

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

题解

暴力循环(不符合题意)

首先想到的解法:暴力循环[不符合题意,先用暴力方法理一理思路,然后我们再想办法,怎么满足题目要求]。实现步骤:

  1. 考虑corner case:有序数组为空,直接返回{-1,-1};
  2. 对数组进行两次遍历,第一次找第一个等于target的元素,第二次找最后等于target的元素;
    1. 从头到尾,依次判断元素是否等于target,如果等于,设置left的值;否则,继续循环;如果循环结束,仍然找不到等于target的元素,直接返回{-1,-1},结束程序运行;
    2. 找到了第一个等于target的元素,然后从后往前遍历,找最后一个等于target的元素,左边界为left;此时一定能找到一个等于target的元素(最差情况,left和right指向同一个元素)
    3. 返回结果数组;

代码:

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()) return {-1, -1};
        int first = -1, last = -1;
        
        int i = 0;
        for ( ; i< nums.size(); i++){
            if (nums[i] == target){
                first = i;
                break;
            }
        }
        if (i  >= nums.size())
            return {-1, -1};
        for (int j=(int)(nums.size()-1); j>= i; j--){
            if (nums[j] == target){
                last = j;
                break;
            }
        }
        return {first, last};
    }
};

二分法

题目给定有序数组,然后题目要求查找给定元素-> 二分法。不过需要对二分法进行改造,原来的方法只要找到target即可,现在我们需要对二分法找到元素时进行限制,限制它是第一个或最后一个等于target的元素。具体变换的部分就是当nums[mid] == target时,我们对边界的处理方法

我们使用两个函数,一个用于查找第一个等于target的元素;一个用于查找最后一个等于target的元素。

findFirst(nums, target)函数:二分法

  1. corner case,数组为空,直接返回-1;表示数组中没有等于target元素;
  2. mid = left + (right - left)/2: 为了避免使用(left + right)/2时,left+right加法运算数据溢出;
  3. 比较nums[mid]和target大小:
    1. nums[mid] < target : left = mid + 1;
    2. nums[mid] > target: right = mid -1;
    3. nums[mid] == target: 要保证是第一个,所以只有当mid=left(说明是第一个);nums[mid-1] !=target,(说明是第一个),找到了;否则,right=mid-1;

findLast(nums, target)函数:和findFirst函数类似,修改nums[mid]==target的情况,要保证下标mid为最后一个等于target的元素:mid==right(最后的位置) || nums[mid+1] != target(手动确定,是最后一个等于target的元素);否则,设置查找左边界。

最后,主函数中,直接调用两个函数即可实现查找功能。

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

    int idx = -1, left = 0, right = nums.size() - 1;

    while (left <= right){
        int mid = left + (right - left)/2;

        if (nums[mid] == target){
            if (mid == right || (mid < right && nums[mid+1] != target)){
                idx = mid;
                break;
            }
            else
                left = mid + 1;
        }
        else if (nums[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }

    return idx;
    }
};
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-08-08 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 题解
    • 暴力循环(不符合题意)
      • 二分法
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档