二分法查找

二分查找适用于有序数组中的元素查找，时间复杂度为O(logn)，根据右指针设置的不同可以有两种不同的写法。

第一种也是我主要记忆的方法就是左闭右闭区间查找，右指针指向nums.size() - 1，这种方法的重要特征是循环条件while(l <= r), 当左边与右边相等时是有比较意义的，因为本来就需要看两边的值。
这种实现方式的C++代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int BinarySearch(vector<int> nums, int target){
	int l = 0, r = nums.size() - 1;
	while (l <= r){
		int mid = (l + r) >> 1;
		if (nums[mid] == target)
			return mid;
		else if (num[mid] < target){
			r = mid + 1;
		}
		else{
			l = mid - 1;
		}	
	}
	return -1;
}

第二种就是采用左闭右开的方法，将右指针指向数组最后一个元素的下一位。采用这种方式，当l $=$ r时再比较是没有意义的，所以只需while(l < r)即可，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int BinarySearch(vector<int>& nums, int target){
	int l = 0, r = nums.size(); // 注意这里的r和之前不同了
	while (l < r){
		int mid = (l + r) >> 1;
		if (nums[mid] == target)
			return mid;
		else if (nums[mid] < target)
			l = mid + 1;
		else
			r = mid;  // 注意这里的r的更新不同了
	}
	return -1;
}

移除元素

题目描述

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

思路解析

这道题需要思考如何用线性的时间复杂度去解决问题，为此我们需要从前向后扫描数组，在发现val元素时及时移动数组元素，这样就可以达到线性的时间复杂度。

然后可以注意到，从左向右扫描元素的过程中，非val元素需要往左边移动的格子数从0一直累加自增，每发现一个val元素就会增加1，所以这里引出第一种方法：记录移动位置数。

1
2
3
4
5
6
7
8
9
10
11
int removeElement(vector<int>& nums, int val) {
	int offset = 0; // 记录后续元素的偏移量
	for (int i = 0; i < nums.size(); i++){
		if (nums[i] == val){
			offset++;
			continue;
		}
		nums[i - offset] = nums[i];
	}
	return nums.size() - offset;
}

还有一种很巧妙但很常用的方法，那就是使用快慢双指针进行求解，快指针用来遍历数组判断条件，慢指针用来记录新数组更新的位置,因为快指针永远不会落后于慢指针，所以慢指针的更新不会影响到快指针的判断。下面是代码，非常简洁：

1
2
3
4
5
6
7
8
9
int removeElement(vector<int>& nums, int val) {

	int fp = 0, sp = 0;
	for (fp; fp < nums.size(); fp++){
		if (nums[fp] == val) continue;
		nums[sp++] = nums[fp];
	}
	return sp;
}