劍指offer53.1——在排序陣列中查找數字（LeetCode34：在排序陣列中查找元素的起始位置）：思路分享
《劍指offer》題目和LeetCode主站本質是一樣的，想要找到target數目，也需要找到左右邊界
題目決議：
在一個排序陣列中，找到
target的左右邊界，從而得到target的數量
第一感覺：二分查找，因為陣列是有序的
靈感閃現！！！ 靈感閃現！！！ 靈感閃現！！！
給定一個數字
target，找到它在排序陣列中插入的位置！！！
這道題就是二分插入！你品，你細品！
下面說一下具體思路和步驟：
- 二分查找的基本形式，邊界、判斷條件構建
- 首先找右邊界：將二分判斷的條件修改為
nums[mid]<=target，最后回傳i作為右邊界 - 同理找到左邊界：二分條件設成
nums[mid]<target，回傳j作為左邊界
優化前代碼如下：
*代碼實作的是《劍指offer》版本，LeetCode只需將邊界裝進陣列回傳即可
class Solution {
public int search(int[] nums, int target) {
//二分邊界構建
int i=0,j=nums.length-1;
int mid;
//回圈條件
while(i<=j) {
mid=(i+j)>>1;
//舍棄所有小于等于target的值，保證i是第一個右邊界
if(nums[mid]<=target) i=mid+1;
else j=mid-1;
}
int right=i;
//判斷是否真的存在target
if(j>=0 && nums[j]!=target ) return 0;
i=0;
while(i<=j) {
mid=(i+j)>>1;
//舍棄所有大于等于target的值，保證j是左邊界
if(nums[mid]<target) i=mid+1;
else j=mid-1;
}
int left=j;
return right-left-1;
}
}
優化后的思想：
- 第一步找到
target在陣列中插入的位置 - 第二步找到
（target-1）在陣列中插入的位置 - 兩個位置直接相減，就可以得到結果
注意：這里無論尋找的值（target）是否存在，都能夠找到合適的索引將其插入陣列！也就是開篇的那個想法
優化后的代碼如下：
class Solution {
public int search(int[] nums, int target) {
int i=0, j=nums.length-1;
return (helper(nums,target,i,j)-helper(nums,target-1,i,j));
}
private int helper(int[] nums,int target,int i,int j) {
while(i<=j) {
int mid=(i+j)>>1;
if(nums[mid] <= target) i=mid+1;
else j=mid-1;
}
return i;
}
}
復雜度分析：
- 時間復雜度為O(logn)，因為是用到二分思想
- 空間復雜度為O(1)，并沒有使用額外空間
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/244272.html
標籤：java
上一篇：用java實作簡單的銀行管理系統
下一篇：jdk15的安裝與配置