文章目錄
-
- JZ6、旋轉數組的最小數
- 面試題53-I 數字在排序數組中出現的次數
- 面試題53-II. 0～n-1中缺失的數字
JZ6、旋轉數組的最小數
題目描述
把一個數組
最開始的若幹個元素
搬到數組的末尾，我們稱之為數組的旋轉。
輸入一個
非遞減排序
的數組的一個旋轉，輸出旋轉數組的最小元素。
NOTE：給出的所有元素都大于0，若數組大小為0，請傳回0。
示例1
輸入
[3,4,5,1,2]
傳回值
1
注：
1、
非遞減排序
：這裡有些歧義，暫且當做
遞增排序
來處理。
2、這裡定義的
旋轉
：比如說{3,4,5,1,2}是{1,2,3,4,5}的一個旋轉，旋轉後第一個元素
大于等于
最後一個元素。
3、
最開始的若幹個元素
：若幹個可以是
0個
，若是0個，則旋轉後的數組就是原遞增數組，就不存在：第一個元素
大于等于
最後一個元素。
題解：
本題是找出最小數，即首先是一個
查找題
，
又因為旋轉後的數組實際上可
劃分為兩個（遞增）排序子數組
（比如：示例的[3,4,5]和[1,2]），即，本題的數組
在一定程度上是排序
的，而排序的數組可以用
二分法
實作查找。
或者說：
如果能夠明确二分之後，答案存在于二分的某一側，就可以使用二分。
關鍵點：
1、二分查找的關鍵是arr[mid]跟誰比。
原則是arr[mid]跟某個值比後能産生二分效果
（即，一次比較後能夠确定答案在mid的某一側）
2、一般的比較原則有：
—如果有目标值target，那麼直接讓arr[mid] 和 target 比較即可。
—如果沒有目标值，就看arr[mid]跟某個值比後能産生二分效果，一般可以考慮
端點
下面以
右端點看作target
來進行分析（也可将左端點 或 左右兩個端點作為target ）
1、情況1：
arr[mid] > target
比如旋轉數組4 5 6 1 2 3 ：arr[mid] 為 6， target為右端點 3， arr[mid] > target，說明arr[mid]處于前邊的遞增子數組， 說明[first … mid] 都是 >= target 的，可以确定最小數在arr[mid]右側，在[mid+1…last]區間内，是以 first = mid + 1
2、情況2：
arr[mid] < target,
比如旋轉數組5 6 1 2 3 4：說明arr[mid]處于後邊的遞增子數組，可以确定最小數在arr[mid]及其左側，說明答案肯定不在[mid+1…last]，但是arr[mid] 有可能是答案,是以答案在[first, mid]區間，是以last = mid;
3、情況3：
arr[mid] == target:
如果是 1 0 1 1 1， arr[mid] = target = 1, 顯然答案在左邊
如果是 1 1 1 0 1, arr[mid] = target = 1, 顯然答案在右邊
是以這種情況，不能确定答案在左邊還是右邊，那麼就讓last = last - 1;慢慢縮少區間，同時也不會錯過答案。
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {if (rotateArray.size() == 0) return 0;
int first = 0, last = rotateArray.size() - 1;
while (first < last) { // 最後剩下一個元素，即為答案
if (rotateArray[first] < rotateArray[last]) { // 提前退出：将前0個元素搬到數組末尾的情況；
return rotateArray[first];
}
int mid = (first + last)/2;
if (rotateArray[mid] > rotateArray[last]) { // 情況1
first = mid + 1;
}
else if (rotateArray[mid] < rotateArray[last]) { //情況2
last = mid;
}
else { // 情況3
--last;
}
}
return rotateArray[first];
}
};
時間複雜度：二分，是以為O(longN)， 但是如果是[1, 1, 1, 1],會退化到O(n)（last = last - 1：一個一個的縮小，縮小n次）
空間複雜度：沒有開辟額外空間，為O(1)
面試題53-I 數字在排序數組中出現的次數
題目：
統計一個數字在
排序數組
中出現的次數。
示例 1:
輸入: nums = [5,7,7,8,8,10], target = 8
輸出: 2
示例 2:
輸入: nums = [5,7,7,8,8,10], target = 6
輸出: 0
題解：
模式識别:
排序數組+一次數出現次數（即，查找一個數出現次數）----------->
二分查找
思路一：
使用二分查找查找出一個給定數（O(logn)），然後從這個數開始用向兩邊周遊，統計重複的次數，因給定數在長度為n的數組中可能出現n次，是以相連變掃描的時間複雜度為O（n）,這和直接從頭掃描整個數組一樣為O（n）。
思路二：(分别查找重複數字的第一個和最後一個)
記重複數字的第一個為左邊界，最後一個為右邊界；
具體步驟（以查右邊界為例）：
1、nums[mid]<target：右邊界在後半段，即left=mid+1；
2、nums[mid]>target：右邊界在前半段，即right=mid-1；
3、nums[mid]==target：此時需判斷這個值是不是右邊界，
3.1 若nums[mid]位于數組的右邊界（即，mid ==(nums.size()-1），或者nums[mid]和它後一位不相等（nums[mid]!=nums[mid+1]），此時nums[mid]是右邊界
3.2 否則，nums[mid]不是右邊界，右邊界在後半段left=mid+1；
代碼：
class Solution {
public:
int search(vector<int>& nums, int target) {
if(nums.size()==0) return 0;//判特
int left=0, right=nums.size()-1, mid;
//找右邊界，跳出循環後mid代表右邊界
while(left<=right){
mid=left+(right-left)/2;
if(nums[mid]<target) left=mid+1;
else if(nums[mid]>target) right=mid-1;
else{
if(mid==(nums.size()-1) ||nums[mid]!=nums[mid+1]) break;
else left=mid+1;
}
}
// 若數組中無 target ，則提前傳回
//mid指向最後查找的位置，若nums[mid]!=target則表明數組沒有target值；
if(nums[mid]!=target) return 0;
//記錄右邊界值
int r=mid;//下面還會進行一次查找，mid會變，是以這裡記錄右邊界值
left=0,right=nums.size()-1;
//找左邊界，跳出循環後mid代表左邊界
while(left<=right){
mid=left+(right-left)/2;
if(nums[mid]<target) left=mid+1;
else if(nums[mid]>target) right=mid-1;
else{
if(mid==0 ||nums[mid]!=nums[mid-1]) break;
else right=mid-1;
}
}
//記錄左邊界值
int l=mid;
return r-l+1;
}
};
時間複雜度 O(log N)： 二分法為對數級别複雜度。
空間複雜度 O(1) ： 幾個變量使用常數大小的額外空間。
面試題53-II. 0～n-1中缺失的數字
題目：
一個長度為n-1的
遞增排序數組
中的所有數字都是唯一的，并且每個數字都在範圍0～n-1之内。在範圍0～n-1内的n個數字中有且隻有一個數字不在該數組中，請
找出
這個數字。
限制：
1 <= 數組長度 <= 10000
示例 1:
輸入: [0,1,3]
輸出: 2
示例 2:
輸入: [0,1,2,3,4,5,6,7,9]
輸出: 8
題解：
模式識别
：排序數組+找出（查找）------>二分查找
思路：
即，
查找第一個下标與其值不同的元素，其下标就是缺失的值；
有一種特殊情況：
當 nums 缺失的是第 n-1 個數時，比如 nums = [0, 1]，此時 nums 缺失的是 2，但所有元素都是nums[index]==index，是以沒有第一個下标和值不同的元素；
代碼：C++，使用帶等号的二分查找while(i<=j)
class Solution {
public:
int missingNumber(vector<int>& nums) {
int n=nums.size();
int left=0,right=n-1,mid;
while(left<=right){
mid=left+(right-left)/2;
if(nums[mid]==mid) left=mid+1;
else{
if(mid==0 || nums[mid-1]==mid-1) return mid;
else right=mid-1;
}
}
//循環結束也沒查找成功，原因是當 nums 缺失的是第 n-1 個數時，比如 nums = [0, 1]，此時 nums 缺失的是 2，但所有元素都是nums[mid]==mid，是以查找不到第一個下标和值不同的元素；循環到最後mid指向最後一個元素，而left=mid+1則是缺失的元素；
return left;
}
};
間複雜度 O(log N)： 二分法為對數級别複雜度。
空間複雜度 O(1)： 幾個變量使用常數大小的額外空間。
Java，不使用帶等号的二分查找while(i < j)
class Solution {
public int missingNumber(int[] nums) {
int i = 0 , j = nums.length - 1;
int mid;
while(i < j){
mid = (i + j)/2;
if(nums[mid] == mid) i++;
else j = mid;
}
if(nums[i] != i) return i;
else return nums.length;
}
}
- 更好了解的寫法：
class Solution {
public int missingNumber(int[] nums) {
if(nums[nums.length - 1] == nums.length - 1) return nums.length;
if(nums[0] != 0) return 0;
int low = 0 , high = nums.length - 1 , mid = 0;
while(low <= high){
mid = low + (high - low) / 2;
if(nums[mid] == mid) low = mid + 1;
else{
if(nums[mid - 1] == mid - 1) break;
else high = mid - 1;
}
}
return mid;
}
}
注：
二分查找循環條件帶不帶等号的差別，即while（i<=j）和while(i < j)
- while（i<=j），區間縮小到 i =j，可能會陷入到死循環，是以，需要return 語句或
break
- while(i < j)，區間縮小到 i =j，不滿足 while(i < j)，即自動退出循環，while循環内一般不需要return語句。