day01 二分，移除元素

题目链接：leetcode704-二分查找, leetcode27-移除元素

二分

注意事项：开闭区间
如果右闭，则right=len(nums)-1, for left <= right {}, right=mid-1
如果右开，则right=len(nums),  for left < right {},  right=mid

Go

左开右闭合: [left, right]

func search(nums []int, target int) int {
	left, right := 0, len(nums)-1
	mid := 0
	for left <= right {
		mid = ((right - left) >> 1) + left

		if nums[mid] < target {
			// 说明target在mid右边，mid向右边移动
			left = mid + 1
		} else if nums[mid] > target {
			// 说明target在mid左边，mid向左边移动
			right = mid - 1
		} else {
			return mid
		}
	}

	return -1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

左闭右开：[left, right)

func search(nums []int, target int) int {
	left, right := 0, len(nums)
	mid := 0
	for left < right {
		mid = ((right - left) >> 1) + left
		if nums[mid] < target {
			// 说明target在mid右边, mid右边移动
			left = mid + 1
		} else if nums[mid] > target {
			// 说明target在mid左边，mid左边移动
			right = mid
		} else {
			return mid
		}
	}
	return -1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Rust

左开右闭合: [left, right]
之所以使用i32是因为当mid为0时, mid-1会报错(Vector的索引是usize类型)

	pub fn search(nums: Vec<i32>, target: i32) -> i32 {
		let (mut left, mut right, mut mid) = (0, (nums.len() - 1) as i32, 0);

		while left <= right {
			mid = ((right - left) >> 1) + left;
			if nums[mid as usize] < target {
				// 说明target在右区间
				left = mid+1;
			} else if nums[mid as usize] > target {
				// 说明target在左边区间
				right = mid -1 ;
			} else {
				return mid as i32;
			}
		}
		return -1;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

左闭右开：[left, right)

	pub fn search(nums: Vec<i32>, target: i32) -> i32 {
		let (mut left, mut right, mut mid) = (0usize, nums.len() - 1, 0usize);

		while left < right {
			mid = ((right - left) >> 1) + left;
			if nums[mid] < target {
				// 说明target在右区间
				left = mid+1;
			} else if nums[mid] > target {
				// 说明target在左边区间
				right = mid;
			} else {
				return mid as i32;
			}
		}
		return -1;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

移除元素

数组的长度是固定的，无法进行删除，所谓的元素删除也只是将目标val移动到数组的末尾作为无效的值，同时对数组中有效值的数量进行标识，如数组所允许访问的索引范围为[0, 有效值的数量)。

Go

双指针法，不再关系无效的val，让有效的val从索引为0开始重组数组（无效的值会被覆盖，不再关心）
如果不想无效的val被覆盖，可以参考相向双指针法，将无效的val全都移动到数组的尾部

func removeElement(nums []int, val int) int {
	idx, numLen := 0, len(nums)
	for fast := 0; fast < numLen; fast++ {
		if nums[fast] == val {
			continue
		}
		nums[idx] = nums[fast]
		idx++
	}
	return idx
}
1
2
3
4
5
6
7
8
9
10
11

相向双指针法，将无效的val全都移动到数组的尾部, 但是数组中的值的顺序会发生变化
基本思路：

1. 存在双指针:left, right，left从索引为0的位置向数组尾部移动，right从索引为len(nums)-1的位置开始向数组头部移动
2. 让left发现指定的val，停止不动，当right发现非指定的val，停止不动
3. 交换left和right所指向的值
4. 重复2,3过程，直到left > right跳出循环

func removeElement(nums []int, val int) int {
	left, right := 0, len(nums)-1

	for left <= right {
		// left指向val的位置
		for left <= right && nums[left] != val {
			left++
		}

		// right指向非val的位置
		for left <= right && nums[right] == val {
			right--
		}

		// 如果移动之后依旧满足left < right, 则交换left和right所指向的值
		if left > right {
			break
		}

		nums[left], nums[right] = nums[right], nums[left]
		left++
		right--
	}

	return left
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

Rust

双指针法

	pub fn remove_element(nums: &mut Vec<i32>, val: i32) -> i32 {
		let mut slow = 0usize;

		for fast in (0..nums.len()) {
			if nums[fast] == val {
				continue
			}
			nums[slow] = nums[fast];
			slow += 1;
		}

		slow as i32
	}
1
2
3
4
5
6
7
8
9
10
11
12
13

相向双指针

	pub fn remove_element(nums: &mut Vec<i32>, val: i32) -> i32 {
		let (mut left, mut right) = (0 , nums.len() as i32 - 1);

		while left <= right {
			// left指向val的位置
			while left <= right && nums[left as usize] != val {
				left += 1;
			}
			// right指向非val的位置
			while left <= right && nums[right as usize] == val {
				// 使用uize，这里可能会报错
				right -= 1;
			}

			if left > right {
				break
			}

			// 交换值
			(nums[left as usize], nums[right as usize]) = (nums[right as usize], nums[left as usize]);
			left += 1;
			right -= 1;

		}

		left
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27