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

leetcode筆記:Search Insert Position

編輯:關於C++

一. 題目描述

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.

[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

二. 題目分析

題目的大意是,給定一個已排序的數組和一個目標值target,如果在數組中找到該目標值,就返回這個目標值的元素下標。如果沒有找到,就返回target應該插入到該數組中的位置下標。這個過程中,假設該數組中沒有重復元素。

和Search for a Range 的解法類似,二分查找即可,可能出問題的地方是對邊界條件的處理。

三. 示例代碼

#include 
#include 

using namespace std;

class Solution {
public:
    int searchInsert(vector& nums, int target) {
        int n = nums.size(), low = 0, high = n - 1, midIndex = 0;
        while (low <= high)
        {
            midIndex = (low + high) / 2;
            if (nums[midIndex] == target)
                return midIndex;
            else if (nums[midIndex] > target)
                high = midIndex - 1;
            else
                low = midIndex + 1;
        }
        // 邊界
        if (low > n)
            return n;
        if (high < 0)
            return 0;
    }
};

解題結果:

這裡寫圖片描述

四. 小結

二分查找的經典題目,對邊界的情況需要額外考慮。該題實際上是實現:std::lower_bound() 的功能。

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