Q35SearchInsertPosition
題目描述
給定一個排序陣列和一個目標值，在陣列中找到目標值，并回傳其索引，如果目標值不存在于陣列中，回傳它將會被按順序插入的位置，
請必須使用時間復雜度為 O(log n) 的演算法，
示例 1:
輸入: nums = [1,3,5,6], target = 5
輸出: 2
示例 2:
輸入: nums = [1,3,5,6], target = 2
輸出: 1
示例 3:
輸入: nums = [1,3,5,6], target = 7
輸出: 4
https://leetcode.cn/problems/search-insert-position
解題思路
首先考慮暴力解法，但暴力的時間復雜度是 O(n) 不符合題目要求，像這種找目標值的首先考慮二分法，二分法要注意的就是 left < right 還是left <= right 的選擇問題和區間縮小時的定界，
解題如下
首先初始化為left=0，right=len，因為陣列長度位置即最后一個元素后面的位置也可為答案，最初的搜索區間為[0, len]，也就是left ~ right，在搜索程序中有如下情況
- 當中間值小于目標值時，mid和mid往左的位置都不是所要找的位置，left應等于mid+1，搜索區間變為[mid+1, right]
- 其余情況，中間值大于等于目標值，那么mid的位置可能是要找的位置，但mid往右絕對不是要找的位置，故right變為mid，搜索區間變為[left, mid]
- 搜索終止時，一定有left==right，也就是區間[left, right]里面一定有要找的位置，此時回傳left或right任一即可，
代碼
public class Q35SearchInsertPosition {
public int searchInsert(int[] nums, int target) {
if(null == nums || nums.length == 0){
return 0;
}
int left = 0;
int right = nums.length;
while(left < right){
int mid = left + (right - left) / 2;
if (nums[mid] < target){
left = mid + 1; //縮小區間為[mid+1, right]
} else {
right = mid; //縮小區間為[left, mid]
}
}
return left;
}
}
本地測驗
public class Q35SearchInsertPositionTest {
private static final Q35SearchInsertPosition q = new Q35SearchInsertPosition();
@Test
public void test1(){
assertEquals(2, q.searchInsert(new int[]{1,3,5,6}, 5));
}
@Test
public void test2(){
assertEquals(1, q.searchInsert(new int[]{1,3,5,6}, 2));
}
@Test
public void test3(){
assertEquals(4, q.searchInsert(new int[]{1,3,5,6}, 7));
}
@Test
public void test4(){
assertEquals(0, q.searchInsert(new int[]{1,3,5,6}, 0));
}
@Test
public void test5(){
assertEquals(0, q.searchInsert(new int[]{1}, 0));
}
}
提交
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/501530.html
標籤：其他