YSMull
<-- algorithm



原题链接

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];
                }
            }
        }
    }
}