C++实现LeetCode(34.在有序数组中查找元素的第一个和最后一个位置)

2024-09-27 18:14:25

[LeetCode] 34. 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].

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]

这道题让我们在一个有序整数数组中寻找相同目标值的起始和结束位置，而且限定了时间复杂度为 O(logn)，这是典型的二分查找法的时间复杂度，所以这里也需要用此方法，思路是首先对原数组使用二分查找法，找出其中一个目标值的位置，然后向两边搜索找出起始和结束的位置，代码如下：

解法一:

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

可能有些人会觉得上面的算法不是严格意义上的 O(logn) 的算法，因为在最坏的情况下会变成 O(n)，比如当数组里的数全是目标值的话，从中间向两边找边界就会一直遍历完整个数组，那么下面来看一种真正意义上的 O(logn) 的算法，使用两次二分查找法，第一次找到左边界，第二次调用找到右边界即可，具体代码如下：

解法二：

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

其实我们也可以只使用一个二分查找的子函数，来同时查找出第一个和最后一个位置。如何只用查找第一个大于等于目标值的二分函数来查找整个范围呢，这里用到了一个小 trick，首先来查找起始位置的 target，就是在数组中查找第一个大于等于 target 的位置，当返回的位置越界，或者该位置上的值不等于 target 时，表示数组中没有 target，直接返回 {-1, -1} 即可。若查找到了 target 值，则再查找第一个大于等于 target+1 的位置，然后把返回的位置减1，就是 target 的最后一个位置，即便是返回的值越界了，减1后也不会越界，这样就实现了使用一个二分查找函数来解题啦，参见代码如下：

解法三：

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

到此这篇关于C++实现LeetCode(34.在有序数组中查找元素的第一个和最后一个位置)的文章就介绍到这了,更多相关C++实现在有序数组中查找元素的第一个和最后一个位置内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

C++实现LeetCode(83.移除有序链表中的重复项)

[LeetCode] 83. Remove Duplicates from Sorted List 移除有序链表中的重复项 Given a sorted linked list, delete all duplicates such that each element appear only once. Example 1: Input: 1->1->2 Output: 1->2 Example 2: Input: 1->1->2->3->3 Output: 1-
C++实现LeetCode(27.移除元素)

[LeetCode] 27. Remove Element 移除元素 Given an array nums and a value val, remove all instances of that value in-place and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with
C++实现LeetCode(30.串联所有单词的子串)

[LeetCode] 30. Substring with Concatenation of All Words 串联所有单词的子串 You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words ex
C++实现LeetCode(25.每k个一组翻转链表)

[LeetCode] 25. Reverse Nodes in k-Group 每k个一组翻转链表 Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. k is a positive integer and is less than or equal to the length of the linked list. If the number of n
C++实现LeetCode(24.成对交换节点)

[LeetCode] 24. Swap Nodes in Pairs 成对交换节点 Given a linked list, swap every two adjacent nodes and return its head. You may not modify the values in the list's nodes, only nodes itself may be changed. Example: Given 1->2->3->4 , you should return t
C++实现LeetCode(31.下一个排列)

[LeetCode] 31. Next Permutation 下一个排列 Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sor
C++实现LeetCode(29.两数相除)

[LeetCode] 29. Divide Two Integers 两数相除 Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator. Return the quotient after dividing dividend by divisor. The integer division should truncate
C++实现LeetCode(26.有序数组中去除重复项)

[LeetCode] 26. Remove Duplicates from Sorted Array 有序数组中去除重复项 Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this
C++实现LeetCode(34.在有序数组中查找元素的第一个和最后一个位置)

[LeetCode] 34. 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
java算法入门之有效的括号删除有序数组中的重复项实现strStr

目录 1.LeetCode 20.有效的括号题目小编菜解思路及算法大神解法 2.LeetCode 26.删除有序数组中的重复项题目小编菜解初版小编菜解改进版思路及算法大神解法 3.LeetCode 28.实现strStr 题目小编菜解大神解法也许,我们永远都不会知道自己能走到何方,遇见何人,最后会变成什么样的人,但一定要记住,能让自己登高的,永远不是别人的肩膀,而是挑灯夜战的自己,人生的道路刚刚启程,当你累了倦了也不要迷茫,回头看一看,你早已不再是那个年少轻狂的少年. 1
C++实现LeetCode(33.在旋转有序数组中搜索)

[LeetCode] 33. Search in Rotated Sorted Array 在旋转有序数组中搜索 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If f
C++实现LeetCode(81.在旋转有序数组中搜索之二)

[LeetCode] 81. Search in Rotated Sorted Array II 在旋转有序数组中搜索之二 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]). You are given a target value to search.
C++实现LeetCode(80.有序数组中去除重复项之二)

[LeetCode] 80. Remove Duplicates from Sorted Array II 有序数组中去除重复项之二 Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length. Do not allocate extra space for another array, you mus
C++实现LeetCode(两个有序数组的中位数)

[LeetCode] 4. Median of Two Sorted Arrays 两个有序数组的中位数 There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). You may assume nums1 and
C++实现LeetCode(108.将有序数组转为二叉搜索树)

[LeetCode] 108.Convert Sorted Array to Binary Search Tree 将有序数组转为二叉搜索树 Given an array where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in wh
java实现向有序数组中插入一个元素实例

整理文档,搜刮出一个java实现向有序数组中插入一个元素,稍微整理精简一下做下分享 package cn.jbit.array; import java.util.*; public class Insert { public static void main(String[] args) { //字符排序 char[] chars = new char[9]; chars[0] = 'a'; chars[1] = 'c'; chars[2] = 'u'; chars[3] = 'b'; cha
PHP实现找出有序数组中绝对值最小的数算法分析

本文实例讲述了PHP实现找出有序数组中绝对值最小的数算法.分享给大家供大家参考,具体如下: 问题: 一个有序数组,值有可能有负值,也有可能没有,现需要找出其中绝对值最小的值. 方法1: 遍历数组,找到绝对值最小值,时间复杂度O(n),n为元素个数. 方法2: 二分查找,因为数组有序,可以利用二分查找,时间复杂度O(logn). 分析步骤: 1. 如果第一个数为正数,说明整个数组没有负数,直接返回第一个数 2. 如果最后一个数为负数,说明整个数组没有正数,直接返回最后一个数 3. 数组元素有正有负

C++实现LeetCode(34.在有序数组中查找元素的第一个和最后一个位置)

[LeetCode] 34. Find First and Last Position of Element in Sorted Array 在有序数组中查找元素的第一个和最后一个位置

相关推荐

随机推荐