文章目录
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
(
l
o
g
n
)
，空间复杂度
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;
}
};