程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> leetcode筆記:Search for a Range

leetcode筆記:Search for a Range

編輯:關於C++

一. 題目描述

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(logn).

If the target is not found in the array, return [-1, -1].

For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4].

二. 題目分析

題目大意是,給定一個已排序的序列和一個目標數字target,在這個序列中尋找等於target元素的下標范圍。由於序列已經排好序,直接用二分查找,分別求等於target的最靠左的元素下標left和最靠右的元素下標right即可。

三. 示例代碼

#include 
#include 

using namespace std;

class Solution {
public:
    vector searchRange(vector& nums, int target) {
        int n = nums.size();
        int left = searchRangeIndex(nums, target, 0, n - 1, true);
        int right = searchRangeIndex(nums, target, 0, n - 1, false);
        vector result;
        result.push_back(left);
        result.push_back(right);
        return result;
    }

private:
    int searchRangeIndex(vector& nums, int target, int low, int high, bool isLeft)
    {
        while (low <= high)
        {
            int midIndex = (low + high) >> 1;
            if (nums[midIndex] == target)
            {
                int temp = -1;
                if (isLeft)
                {
                    if (nums[midIndex] == nums[midIndex - 1] && low < midIndex)
                        temp = searchRangeIndex(nums, target, low, midIndex - 1, true);
                }
                else
                {
                    if (nums[midIndex] == nums[midIndex + 1] && high > midIndex)
                        temp = searchRangeIndex(nums, target, midIndex + 1, high, false);
                }
                return temp == -1 ? midIndex : temp; // temp == -1時表示只有中間一個值等於target
            }
            else if (nums[midIndex] > target)
                high = midIndex - 1;
            else
                low = midIndex + 1;
        }

        return -1; // 找不到target,輸出-1

    }
};

這裡寫圖片描述

四. 小結

注意題目要求O(logn)的時間復雜度,算法寫的不好可能會超時。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved