文章目錄
-
- 1. 題目來源
- 2. 題目說明
- 3. 題目解析 --- I. 在排序數組中查找數字 I
-
- 方法一：周遊+正常解法
- 方法二：二分法+遞歸+巧妙解法
- 4. 題目解析 --- II. 0～n-1中缺失的數字
-
- 4.1 方法一：周遊+正常解法
- 方法二：二分法+巧妙解法
1. 題目來源
連結：I. 在排序數組中查找數字 I
連結：II. 0～n-1中缺失的數字
來源：LeetCode——《劍指-Offer》專項
2. 題目說明
3. 題目解析 — I. 在排序數組中查找數字 I
方法一：周遊+正常解法
順序周遊即可。時間複雜度 O ( n ) O(n) O(n)，空間複雜度 O ( 1 ) O(1) O(1)。沒有用到 排序數組 的特性。
參見代碼如下：
// 執行用時 :4 ms, 在所有 C++ 送出中擊敗了98.65%的使用者
// 記憶體消耗 :15.8 MB,在所有 C++ 送出中擊敗了100.00%的使用者
class Solution {
public:
int search(vector<int>& nums, int target) {
if (nums.size() == 0) return 0;
int tmp = 0;
for (int i = 0; i <nums.size(); ++i) {
while (i < nums.size() and nums[i] == target) {
++tmp;
++i;
}
}
return tmp;;
}
};
方法二：二分法+遞歸+巧妙解法
二分法的巧妙應用，現以找連續出現數字的第一個位置為例，主要思路如下：
- 每次拿中間數字
nums[mid]
target
- 若
nums[mid] > target
target
right = mid - 1
- 若
nums[mid] < target
target
left = mid + 1
- 若
nums[mid] == target
target
target
target
target
right = mid - 1
- 若
至此，即可采用二分+遞歸的思想解決這個問題了，關于最後一個
target
的位置查找與上面的思想基本一緻，在此不列出，可自行思考。
時間複雜度 O ( l o g n ) O(logn) O(logn)，空間複雜度 O ( 1 ) O(1) O(1)
是以，遇到排序數組或者能轉化成排序數組的形式，二分法是降低時間複雜度的利器！
參見代碼如下：
// 執行用時 :16 ms, 在所有 C++ 送出中擊敗了22.43%的使用者
// 記憶體消耗 :23.7 MB, 在所有 C++ 送出中擊敗了100.00%的使用者
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = getLeft(nums, target, 0, nums.size() - 1);
int right = getRight(nums, target, 0, nums.size() - 1);
if (left > -1 and right > -1) return right - left + 1;
return 0;
}
int getLeft(vector<int> nums, int target, int left, int right) {
if (left > right) return -1;
int mid = (left + right) >> 1;
if (nums[mid] == target) {
if ((mid > 0 and nums[mid - 1] != target) or mid == 0) return mid;
else right = mid - 1;
}
else if (nums[mid] > target) right = mid - 1;
else left = mid + 1;
return getLeft(nums, target, left, right);
}
int getRight(vector<int> nums, int target, int left, int right) {
if (left > right) return -1;
int mid = (left + right) >> 1;
if (nums[mid] == target) {
if ((mid < nums.size() - 1 and nums[mid + 1] != target) or mid == nums.size() - 1) return mid;
else left = mid + 1;
}
else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
return getRight(nums, target, left, right);
}
};
4. 題目解析 — II. 0～n-1中缺失的數字
4.1 方法一：周遊+正常解法
暴力法，周遊數組，數字在數組中，其下标與目前數組所存放的值相同，若不相同，則傳回數組下标即可。若周遊完數組仍為傳回，說明數組有序，最後一個數字是缺失數字，則需要傳回數組末尾存放的數字再加一即可。時間複雜度 O ( n ) O(n) O(n)，空間複雜度 O ( 1 ) O(1) O(1)。
// 執行用時 :24 ms, 在所有 C++ 送出中擊敗了58.30%的使用者
// 記憶體消耗 :19.5 MB, 在所有 C++ 送出中擊敗了100.00%的使用者
class Solution {
public:
int missingNumber(vector<int>& nums) {
for (int i = 0; i < nums.size(); ++i) {
if (i != nums[i])
return i;
}
return nums.back() + 1;
}
};
方法二：二分法+巧妙解法
類比在有序數組查找某數是否存在一個性質。
參見代碼如下：
// 執行用時 :20 ms, 在所有 C++ 送出中擊敗了82.48%的使用者
// 記憶體消耗 :19.5 MB, 在所有 C++ 送出中擊敗了100.00%的使用者
class Solution {
public:
int missingNumber(vector<int>& nums) {
int left = 0, right = nums.size();
while (left < right) {
int mid = (left + right) >> 1;
if (mid == nums[mid]) left = mid + 1;
else right = mid;
}
return left;
}
};