- 個人博客：https://javaniuniu.com/
- 難度：
簡單 - 本題涉及算法：
二分查找 - 思路：
二分查找暴力目標(biāo)值插入數(shù)組 - 類似題型：
題目 35. 搜索插入位置
給定一個排序數(shù)組和一個目標(biāo)值惨撇，在數(shù)組中找到目標(biāo)值廊鸥，并返回其索引件豌。如果目標(biāo)值不存在于數(shù)組中，返回它將會被按順序插入的位置斤寇。
你可以假設(shè)數(shù)組中無重復(fù)元素。
示例 1:
輸入: [1,3,5,6], 5
輸出: 2
示例 2:
輸入: [1,3,5,6], 2
輸出: 1
示例 3:
輸入: [1,3,5,6], 7
輸出: 4
示例 4:
輸入: [1,3,5,6], 0
輸出: 0
方法一 二分查找
-
復(fù)雜度分析：
- 時間復(fù)雜度
，這里
是數(shù)組的長度危号，每一次都將問題的規(guī)氖膊縮減為原來的一半票彪，因此時間復(fù)雜度是對數(shù)級別的
- 空間復(fù)雜度
- 時間復(fù)雜度
python
class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
left , right = 0, len(nums)
while left < right:
mid = left + (right - left)/2
if nums[mid] < target:
left = mid + 1
else:
right = mid
return left
方法二 暴力遍歷
-
復(fù)雜度分析：
- 時間復(fù)雜度
- 空間復(fù)雜度
- 時間復(fù)雜度
python
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
if not nums:
return 0
if nums[-1] < target:
return len(nums)
for i in range(len(nums)):
if nums[i] >= target:
return i
java
class Solution {
public int searchInsert(int[] nums, int target) {
int len = nums.length;
int ans = 0;
if (len == 0){
return 0;
}
if (nums[len-1] < target) {
return len;
}
for (int i = 0;i<len;i++) {
if (nums[i] >= target) {
ans = i;
break;
}
}
return ans;
}
}
方法三 目標(biāo)值插入數(shù)組后在查找對于位置（提供了一個新思路）
-
解題思路：
- 目標(biāo)值插入數(shù)組中
- 排序后在查詢對于目標(biāo)值的位置
-
復(fù)雜度分析：
- 時間復(fù)雜度
- 空間復(fù)雜度
- 時間復(fù)雜度
python
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
# 不管這個數(shù)在不在里面摇零，直接append
nums.append(target)
# 然后再排序
nums.sort()
# 最后返回查找的index
return nums.index(target)
