LeetCode 704 二分查找
题目链接: [704 二分查找](704. 二分查找 - 力扣(LeetCode))
思路:
- 根据有序数组、无重复元素条件基本可以判断使用二分法
- 确定区间的定义,一般分为两种写法,一种是左闭右闭即 left
target
right,另一种是左闭右开即 left
target < right
二分法第一种写法
定义 target 是在一个在左闭右闭的区间里,也就是[left, right]
要点:
- while (left <= right) 要使用 <=,left = right的场景是有意义的
- if (nums[middle] > target) right 要赋值为 middle - 1,因为当前这个nums[middle]一定不是target
代码如下:
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(right >= left) {
int middle = left + ((right - left) / 2);
if(nums[middle] > target){
right = middle - 1;
}else if(nums[middle] < target){
left = middle + 1;
}else{
return middle;
}
}
return -1;
}
}
二分法第二种写法
定义 target 是在一个在左闭右开的区间里,**也就是[left, right)
要点:
- while (left <= right) 要使用 <,left = right的场景是无意义的
- if (nums[middle] > target) right 要赋值为 middle,因为右开区间不会去比较nums[middle]
代码如下:
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length;
while(right > left) {
int middle = left + ((right - left) >> 1);
if(nums[middle] > target){
right = middle;
}else if(nums[middle] < target){
left = middle + 1;
}else{
return middle;
}
}
return -1;
}
}
LeetCode 27 移除元素
题目链接: [27 移除元素](27. 移除元素 - 力扣(LeetCode))
思路:
-
暴力破解
两层for循环,外层for循环遍历数组元素 ,里层for循环更新数组。
代码如下:
// 时间复杂度:O(n^2)
// 空间复杂度:O(1)
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int size = nums.size();
for (int i = 0; i < size; i++) {
if (nums[i] == val) { // 发现需要移除的元素,就将数组集体向前移动一位
for (int j = i + 1; j < size; j++) {
nums[j - 1] = nums[j];
}
i--; // 因为下标i以后的数值都向前移动了一位,所以i也向前移动一位
size--; // 此时数组的大小-1
}
}
return size;
}
};
- 双指针法
要点:
定义快指针指向当前循环的nums下标,慢指针指向更新数组下标的位置
代码如下:
class Solution {
public int removeElement(int[] nums, int val) {
int lowIndex = 0;
for(int fastIndex = 0;fastIndex < nums.length;fastIndex++){
if(nums[fastIndex] != val){
nums[lowIndex++] = nums[fastIndex];
}
}
return lowIndex;
}
}