2.LeetCode刷題-搜尋插入位置

語言: CN / TW / HK

小知識,大挑戰!本文正在參與“程式設計師必備小知識”創作活動。

一、題目描述

難度:簡單~

給定一個排序陣列和一個目標值,在陣列中找到目標值,並返回其索引。如果目標值不存在於陣列中,返回它將會被按順序插入的位置。

請必須使用時間複雜度為 O(log n) 的演算法。

示例1:

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

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

c 輸入: nums = [1,3,5,6], target = 7 輸出: 4 示例4:

c 輸入: nums = [1,3,5,6], target = 0 輸出: 0 示例5:

c 輸入: nums = [1], target = 0 輸出: 0

提示:   1 <= nums.length <= 10^4   -10^4 <= nums[i] <= 10^4   nums 為無重複元素的升序排列陣列   -10^4 <= target <= 10^4

作者:力扣 (LeetCode) 連結:https://leetcode-cn.com/leetbook/read/array-and-string/cxqdh/ 來源:力扣(LeetCode) 著作權歸作者所有。商業轉載請聯絡作者獲得授權,非商業轉載請註明出處。

二、題目解析

思路: 直接程式碼裡註釋!

三、程式碼

1.C實現

暴力遍歷:

分兩部分: 第一部分:如果target小於等於陣列中的值,直接return; 第二部分:如果全部遍歷完證明target是最大的數,直接插入末尾,即返回陣列長度即可。 c int searchInsert(int* nums, int numsSize, int target){ for(int i = 0;i < numsSize; i++) { if(target <= nums[i]) return i; } return numsSize; }

缺點:數值較多時,沒有那麼高效,而且沒有滿足題目中的時間複雜度要求【此暴力遍歷時間複雜度為O(N)】!!!為解決這兩個問題,必須使用:二分查詢

二分查詢:

  1. left=0,right=numsSize,取mid為中間值
  2. 每次根據nums[mid]和target之間的大小進行判斷,相等則直接返回下標,nums[mid] < target則left = mid + 1,nums[mid] > target,則right = mid - 1.
  3. 查詢結果如果沒有相等則返回left, 該值為插入位置。   時間複雜度為:O(logN),因為每次迴圈都會丟棄一半的查詢空間。

c int pivotIndex(int* nums, int numsSize) { int left = 0, right = numsSize-1; while(left <= right) { //防止整型溢位 int mid = left + (right - left) / 2; if(nums[mid] == target) return mid; else if(nums[mid] < target) left = mid + 1; else if(nums[mid] > target) right = mid - 1; } return left; }

2.C++實現

實現上述二分查詢。

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

3.Python實現

實現上述二分查詢。 python class Solution: def searchInsert(self, nums: List[int], target: int) -> int: left = 0 right = len(nums) - 1 while(left <= right): mid = (left + right) // 2 # // 為向下取整 if(nums[mid] == target): return mid elif(nums[mid] < target): left = mid + 1 else: right = mid - 1 return left

🔆In The End!

請新增圖片描述

| 從現在做起,堅持下去,一天進步一小點,不久的將來,你會感謝曾經努力的你! | | ------------------------------------ |

本博主會持續更新爬蟲基礎分欄及爬蟲實戰分欄,認真仔細看完本文的小夥伴們,可以點贊收藏並評論出你們的讀後感。並可關注本博主,在今後的日子裡閱讀更多爬蟲文!

如有錯誤或者言語不恰當的地方可在評論區指出,謝謝!\ 如轉載此文請聯絡我徵得本人同意,並標註出處及本博主名,謝謝 !