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

LeetCode Search Insert Position

編輯:C++入門知識

LeetCode Search Insert Position


LeetCode解題之Search Insert Position


原題

在一個有序數組中,如果目標數字存在,則返回它的下標,否則返回它應該插入位置的下標值。

注意點:

數組中沒有重復數字

例子:

輸入: nums = [1, 3, 5, 6], target = 5
輸出: 2

輸入: nums = [1, 3, 5, 6], target = 2
輸出: 1

解題思路

又是一道二分搜索的題。分以下幾種情況:如果當前數字是目標數字,或者當前數字大於目標數字而它之前的數字小於目標數字,則返回當前下標;如果當前數字為最後一個且它比目標數字小,則返回當前下標的後一位。

AC源碼

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        length = len(nums)
        start = 0
        end = length
        while start < end:
            mid = (start + end) // 2
            if nums[mid] == target or (nums[mid] > target 
                and (mid == 0 or nums[mid - 1] < target)):
                return mid
            if mid == length - 1 and nums[mid] < target:
                return mid + 1
            if nums[mid] < target:
                start = mid + 1
            else:
                end = mid


if __name__ == "__main__":
    assert Solution().searchInsert([1, 3, 5, 6], 5) == 2
    assert Solution().searchInsert([1, 3, 5, 6], 2) == 1
    assert Solution().searchInsert([1, 3, 5, 6], 7) == 4
    assert Solution().searchInsert([1, 3, 5, 6], 0) == 0

歡迎查看我的Github來獲得相關源碼。


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