有关数组的leetcode经典题型
编号01：删除重复的元素
这是LC的第一题，这题在Rust中有专门的实现方法，那就是Vec::dedup。我们今天来分析一下Rust是如何实现的
impl<T, A> Vec<T, A> where
T: PartialEq<T>,
A: Allocator,
{
pub fn dedup(&mut self) {
self.dedup_by(|a, b| a == b)
}
pub fn dedup_by<F>(&mut self, same_bucket: F)
where F: FnMut(&mut T, &mut T) -> bool
{
let len = {
let (dedup, _) = self.as_mut_slice()
.partition_dedup_by(same_bucket);
dedup.len()
};
self.truncate(len);
}
// 提取整个向量的可变片段，相当于 &mut s[..]
pub fn as_mut_slice(&mut self) -> &mut [T] {
self
}
}
slice::partition_dedup_by
将除第一个连续元素外的所有元素移动到满足给定相等关系的切片的末尾。
返回两个切片。第一个不包含连续的重复元素。第二个包含所有的副本，没有指定顺序。
same_bucket 函数从切片中传递对两个元素的引用，并且必须确定这些元素是否相等。元素的传递顺序与它们在slice中的顺序相反，所以如果same_bucket(a, b)返回true，则a被移到slice的最后。
如果切片已排序，则第一个返回的切片不包含重复的部分。
举例：
#![feature(slice_partition_dedup)]
let mut slice = ["foo", "Foo", "BAZ", "Bar", "bar", "baz", "BAZ"];
let (dedup, duplicates) = slice.partition_dedup_by(|a, b|
a.eq_ignore_ascii_case(b));
assert_eq!(dedup, ["foo", "BAZ", "Bar", "baz"]);
assert_eq!(duplicates, ["bar", "Foo", "BAZ"]);
函数声明：
pub fn partition_dedup_by<F>(&mut self, same_bucket: F) -> (&mut [T], &mut [T])
where F: FnMut(&mut T, &mut T) -> bool, {
}
虽然我们对self有一个可变的引用，但我们不能做任意的改变。same_bucket的调用可能会引起panic崩溃，所以我们必须确保切片slice始终处于有效状态。
我们处理这个问题的方法是使用swaps交换；我们对所有元素进行迭代，边走边交换，所以最后我们希望保留的元素在前面，而我们希望拒绝的元素在后面。然后我们就可以分割切片了。这个操作仍然是O(n)。
举个例子。我们从这个状态开始，其中r代表 “next_read“，w代表 “next_write“。
r
+---+---+---+---+---+---+
| 0 | 1 | 1 | 2 | 3 | 3 |
+---+---+---+---+---+---+
w
比较self[r]=1和self[w-1]=0，这不是重复的，所以我们交换self[r]和self[w](当r==w时没有影响)，然后同时增加r和w，得到：
r
+---+---+---+---+---+---+
| 0 | 1 | 1 | 2 | 3 | 3 |
+---+---+---+---+---+---+
w
比较self[r]=1和self[w-1]=1，这个值是重复的，所以我们增加’ r ‘，但其他的都保持不变```
r
+---+---+---+---+---+---+
| 0 | 1 | 1 | 2 | 3 | 3 |
+---+---+---+---+---+---+
w
比较self[r]=2和self[w-1]=1，这不是重复的，所以交换self[r]和self[w]并推进r和w
r
+---+---+---+---+---+---+
| 0 | 1 | 2 | 1 | 3 | 3 |
+---+---+---+---+---+---+
w
比较self[r]=3和self[w-1]=2，不重复，所以交换self[r]和self[w]并推进r和w
r
+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 1 | 3 |
+---+---+---+---+---+---+
w
重复，前进r，切片结束。
在w处分割。
- 安全性：
- “
while“条件保证 “next_read“和 “next_write“小于 “len“，因此在 “self“里面 prev_ptr_write指向ptr_write之前的一个元素，但是next_write从1开始，所以prev_ptr_write永远不会小于0，是在片内。这就满足了对ptr_read、prev_ptr_write和ptr_write的派生要求，也满足了使用ptr.add(next_read)、ptr.add(next_write-1)和prev_ptr_write.offset(1)的要求。next_write也是每个循环最多递增一次，这意味着在可能需要交换的时候，没有元素被跳过。ptr_read和prev_ptr_write从不指向同一个元素。这对&mut *ptr_read、&mut *prev_ptr_write来说是安全的。解释很简单，next_read >= next_write永远是真，因此next_read > next_write-1也是真。
- “
pub fn partition_dedup_by<F>(&mut self, mut same_bucket: F) -> (&mut [T], &mut [T])
where F: FnMut(&mut T, &mut T) -> bool,
{
let len = self.len();
if len <= 1 {
return (self, &mut []);
}
let ptr = self.as_mut_ptr();
let mut next_read: usize = 1;
let mut next_write: usize = 1;
unsafe {
// Avoid bounds checks by using raw pointers.
while next_read < len {
let ptr_read = ptr.add(next_read);
let prev_ptr_write = ptr.add(next_write - 1);
if !same_bucket(&mut *ptr_read, &mut *prev_ptr_write) {
if next_read != next_write {
let ptr_write = prev_ptr_write.offset(1);
mem::swap(&mut *ptr_read, &mut *ptr_write);
}
next_write += 1;
}
next_read += 1;
}
}
self.split_at_mut(next_write)
}
slice::split_at_mut
-
在一个索引处将一个可变切片分为两部分
- 第一个将包含来自[0，mid）的所有索引（不包括索引mid本身）
- 第二个将包含来自[mid，len）的所有索引（不包括索引len本身）
-
panic- 若
mid > len就会崩溃
- 若
-
示例
let mut v = [1, 0, 3, 0, 5, 6]; let (left, right) = v.split_at_mut(2); assert_eq!(left, [1, 0]); assert_eq!(right, [3, 0, 5, 6]); left[1] = 2; right[1] = 4; assert_eq!(v, [1, 2, 3, 4, 5, 6]);
pub fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) {
assert!(mid <= self.len());
unsafe { self.split_at_mut_unchecked(mid) }
}
unsafe fn split_at_mut_unchecked(&mut self, mid: usize) -> (&mut [T], &mut [T]) {
let len = self.lenself.split_at_mut_unchecked(mid)();
let ptr = self.as_mut_ptr();
// SAFETY: Caller has to check that `0 <= mid <= self.len()`.
// `[ptr; mid]` and `[mid; len]` are not overlapping, so returning a mutable reference
// is fine.
unsafe { (from_raw_parts_mut(ptr, mid), from_raw_parts_mut(ptr.add(mid), len - mid)) }
}
编号35：搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
- 有序数组，可以试试二分法
- 有重复元素，二分法返回的下标不唯一
- 循环不变量
在计算机科学中，循环不变性（loop invariant，或“循环不变量”），是一组在循环体内、每次迭代均保持为真的性质，通常被用来证明程式或伪码的正确性（有时但较少情况下用以证明算法的正确性）。简单说来，“循环不变性”是指在循环开始和循环中，每一次迭代时为真的性质。这意味着，一个正确的循环体，在循环结束时“循环不变性”和“循环终止条件”必须同时成立。
- 在循环过程中保持不变的量
- 一个循环不变量是指在循环开始和循环中每一次迭代时永远为真的量
- 循环不变式
- 我们把循环不变式认为是一个逻辑断言或者说假设，在一个循环过程中，每一次迭代开始前（或者后）我们都会让这个假设保持为真（true），在循环结束时，就能得到一个最后假设，进而验证算法正确性，它包括三个部分——初始化、保持、终止：
- 初始化：循环初次执行的时候不变式为真
- 保持：如果在某次迭代开始的时候不变式为真，那么在下次迭代开始之前（也就是本次迭代结束后），它也应该保持正确
- 终止：循环正确终止，当循环结束时根据不变式，即得正确性
- 举例
- 我们假设对于外层
for循环每次迭代开始前[0 .. j - 1]数组是有序的来作为循环不变式 - 初始化：
[0 .. 0]有序 - 保持：在
[0 .. j - 1]的基础上，通过每次迭代移动arr[j]到合适位置来保持[0 .. j]有序 j = arr.length时外层for循环终止，整个数组有序即得证
- 我们假设对于外层
- 我们把循环不变式认为是一个逻辑断言或者说假设，在一个循环过程中，每一次迭代开始前（或者后）我们都会让这个假设保持为真（true），在循环结束时，就能得到一个最后假设，进而验证算法正确性，它包括三个部分——初始化、保持、终止：
- 思路
+-----+-----+-----+-----+ | | | | | +-----+-----+-----+-----+ ^ ^ ^ ^ [1] | [2] | [3] | [4] | + + + +- 分析目标值所在位置的所有情况
- 目标值在数组所有元素之前
- 目标值等于数组某个元素
- 目标值应插入数组中的位置
- 目标值在所有元素之后
- 循环不变量：半开半闭区间
- 目标值所在的区间为
[left, right)半开半闭区间
- 目标值所在的区间为
- 分析目标值所在位置的所有情况
- 代码：
过程
对于如下的数组，
+-----+-----+-----+-----+
| 1 | 3 | 5 | 6 |
+--+--+-----+-----+-----+
^ ^
| |
+ +
left right
当 target = 2 时过程为：
+----------------------------------+ +------------------------------------+
| | | |
| while: left(1) < right(4) | | while: left(0) < right(2) |
| | | |
| middle = (0 + 4) / 2 = 2 | | middle = (0 + 2) / 2 = 1 |
| | | |
| +-----+-----+-----+-----+ | | +-----+-----+-----+-----+ |
| | 1 | 3 | 5 | 6 | | | | 1 | 3 | 5 | 6 | |
| +--+--+-----+--+--+-----+ | | +--+--+--+--+--+--+-----+ |
| ^ ^ ^ | | ^ ^ ^ |
| | | | | | | | | |
| + + + | | + + + |
| left middle right | | left middle right |
| | | |
| target(2) < array[middle](5) | | target(2) < array[middle](3) |
| | | |
| right = middle | | right = middle = 1 |
| | | |
| +-----+-----+-----+-----+ | | +-----+-----+-----+-----+ |
| | 1 | 3 | 5 | 6 | | | | 1 | 3 | 5 | 6 | |
| +--+--+-----+--+--+-----+ | | +--+--+--+--+-----+-----+ |
| ^ ^ | | ^ ^ |
| | | | | | | |
| + + | | + + |
| left right | | left right |
| | | |
+----------------------------------+ +------------------------------------+
+------------------------------------+ +------------------------------------+
| | | |
| while: left(0) < right(1) | | while: left[1] < right[1] |
| | | |
| middle = (0 + 1) / 2 = 0 | | break while |
| | | |
| +-----+-----+-----+-----+ | | |
| | 1 | 3 | 5 | 6 | | | index = middle + 1 |
| +--+--+-----+-----+-----+ | | |
| ^ | | index = right |
| +-----+ | | |
| + + | | |
| left middle | | |
| | | |
| target(2) > array[middle](1) | | |
| | | |
| left = middle + 1 = 1 | | |
| | | |
| +-----+-----+-----+-----+ | | |
| | 1 | 3 | 5 | 6 | | | |
| +--+--+--+--+-----+-----+ | | |
| ^ ^ | | |
| | +-----+ | | |
| + + + | | |
| middle right left | | |
| | | |
+------------------------------------+ +------------------------------------+
当 target = 7 的过程为：
+------------------------------------+ +------------------------------------+
| | | |
| while: left(0) < right(4) | | while: left(3) < right(4) |
| | | |
| middle = (0 + 4) / 2 = 2 | | middle = (3 + 4) / 2 = 3 |
| | | |
| +-----+-----+-----+-----+ | | +-----+-----+-----+-----+ |
| | 1 | 3 | 5 | 6 | | | | 1 | 3 | 5 | 6 | |
| +--+--+-----+--+--+-----+ | | +-----+-----+-----+--+--+ |
| ^ ^ ^ | | ^ ^ |
| | | | | | +-----+ | |
| + + + | | + + + |
| left middle right | | left middle right |
| | | |
| target(7) > array[middle](5) | | target(7) > array[middle](6) |
| | | |
| left = middle + 1 = 3 | | left = middle + 1 = 4 |
| | | |
| +-----+-----+-----+-----+ | | +-----+-----+-----+-----+ |
| | 1 | 3 | 5 | 6 | | | | 1 | 3 | 5 | 6 | |
| +-----+-----+-----+--+--+ | | +-----+-----+-----+-----+ |
| ^ ^ | | ^ |
| | | | | +-----+ |
| + + | | + + |
| left right | | left right |
| | | |
+------------------------------------+ +------------------------------------+
+------------------------------------+
| |
| while: left(4) < right(4) |
| |
| break while |
| |
| index = middle + 1 |
| |
| index = right |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
+------------------------------------+
当 target = 0时，过程为：
+------------------------------------+ +------------------------------------+
| | | |
| while: left(0) < right(4) | | while: left(0) < right(2) |
| | | |
| middle = (0 + 4) / 2 = 2 | | middle = (0 + 2) / 2 = 1 |
| | | |
| +-----+-----+-----+-----+ | | +-----+-----+-----+-----+ |
| | 1 | 3 | 5 | 6 | | | | 1 | 3 | 5 | 6 | |
| +--+--+-----+--+--+-----+ | | +--+--+--+--+--+--+-----+ |
| ^ ^ ^ | | ^ ^ ^ |
| | | | | | +- | | |
| + + + | | + + + |
| left middle right | | left middle right |
| | | |
| target(0) < array[middle](5) | | target(0) < array[middle](3) |
| | | |
| right = middle | | rihgt = middle = 1 |
| | | |
| +-----+-----+-----+-----+ | | +-----+-----+-----+-----+ |
| | 1 | 3 | 5 | 6 | | | | 1 | 3 | 5 | 6 | |
| +--+--+-----+--+--+-----+ | | +--+--+--+--+-----+-----+ |
| ^ ^ | | ^ ^ |
| | | | | | | |
| + + | | + + |
| left right | | left rihgt |
| | | |
+------------------------------------+ +------------------------------------+
+------------------------------------+ +------------------------------------+
| | | |
| while: left(0) < right(1) | | while: left(0) < right(0) |
| | | |
| middle = (0 + 1) / 2 = 0 | | break middle = 0 |
| | | |
| +-----+-----+-----+-----+ | | index = middle = 0 |
| | 1 | 3 | 5 | 6 | | | |
| +--+--+----++-----+-----+ | | index = right |
| ^ ^ | | |
| +-----+ +---+ | | |
| + + + | | |
| left middle right | | |
| | | |
| target(0) < array[middle](1) | | |
| | | |
| right = middle = 0 | | |
| | | |
| +-----+-----+-----+-----+ | | |
| | 1 | 3 | 5 | 6 | | | |
| +--+--+-----+-----+-----+ | | |
| ^ | | |
| +-----+ | | |
| + + | | |
| left right | | |
| | | |
+------------------------------------+ +------------------------------------+
源码
use std::cmp::Ordering;
pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
let mut left = 0usize;
let mut right = nums.len();
let mut middle;
while left < right {
middle = left + ((right - left) >> 1);
match nums[middle].cmp(&target) {
Ordering::Less => left = middle + 1,
Ordering::Greater => right = middle,
Ordering::Equal => return middle as i32,
}
}
right as i32
}
或者
pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
nums.binary_search(&target).unwrap_or_else(|x|x) as i32
}
编号27: 移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
快慢指针法
pub fn remove_element(nums: &mut Vec<i32>, val: i32) -> i32 {
let mut fast_index = 0;
let mut slow_index = 0;
'a: while fast_index < nums.len() {
while nums[fast_index] == val {
fast_index += 1;
if fast_index == nums.len() {
break 'a;
}
}
nums[slow_index] = nums[fast_index];
slow_index += 1;
fast_index += 1;
}
slow_index as i32
}
技巧
防止溢出
int middle = left + ((right - left) / 2) ;
int middle = left + ((right - left) >> 1) ;
middle = (left + right) / 2;