2021/04/17
2020-04-17 模板法重做
跟 第81题 思路一样,都是在在标准二分模板里面做一些 预处理。
impl Solution {
pub fn find_min(nums: Vec<i32>) -> i32 {
let last = *nums.last().unwrap();
let mut i = 0;
let mut j = nums.len() - 1;
while i < j {
// begin fix
while i < j && nums[i] == nums[j] {
i += 1;
}
if i == j {
return nums[j];
}
// end fix
let mid = i + (j - i) / 2;
if nums[mid] <= last {
j = mid;
} else {
i = mid + 1;
}
}
return nums[i];
}
}
可以看到,只有 //begin fix 和 //end fix 中间的代码是非模板代码。所以开个玩笑,用 rust 的 unsafe 把非模板代码包起来。
impl Solution {
pub fn find_min(nums: Vec<i32>) -> i32 {
let last = *nums.last().unwrap();
let mut i = 0;
let mut j = nums.len() - 1;
while i < j {
unsafe { // 非模板代码本来就是 unsafe,没毛病
while i < j && nums[i] == nums[j] {
i += 1;
}
if i == j {
return nums[j];
}
}
let mid = i + (j - i) / 2;
if nums[mid] <= last {
j = mid;
} else {
i = mid + 1;
}
}
return nums[i];
}
}
2021-01-23 第一次做
这道 hard 不会套模板,先这样吧。
class Solution {
public int findMin(int[] nums) {
int i = 0;
int j = nums.length - 1;
if (nums[i] < nums[j]) return nums[i];
while (true) {
while (nums[i] == nums[j] && i < j) {
i++;
}
if (nums[i] < nums[j]) return nums[i];
if (i == j || i == j - 1) return nums[j];
int mid = (i + j) / 2;
int n = nums[mid], l = nums[i], r = nums[j];
if (n == l) {
i = mid;
continue;
}
if (n > l) { // n 在上方
if (nums[mid+1] >= nums[mid]) {
i = mid + 1;
} else {
return nums[mid + 1];
}
} else { // n 在下方
if (nums[mid] >= nums[mid - 1]) {
j = mid - 1;
} else {
return nums[mid];
}
}
}
}
}