peak finding 问题

出处

分析

1. 当前元素就是局部最小

2. 当前元素不是局部最小，那么此时，总是会有一边以上的元素小于当前元素。可以自己写一下各种情况

1. 碰到一个局部最小的元素 我们的任务完成了

2. 碰到第一个元素 结论：第一个元素一定是局部最小的元素

我们一定可以在较小的相邻元素那边找到一个局部最小的元素

1D finding

    public static int func(int[] a) {
        if (a.length == 0)
            return -1;
        if (a.length == 1)
            return 0;

        // 判断是否在边界
        if (a[0] > a[1])
            return 0;
        else if (a[a.length - 1] > a[a.length - 1 - 1])
            return a.length - 1;

        // 不在边界就一定在中间
        for (int i = 1; i < a.length - 1; i++) {
            if (a[i] > a[i - 1] && a[i] > a[i + 1])
                return i;
        }

        return -1;
    }

    public static int func2(int[] nums) {
        if (nums == null || nums.length == 0)
            return -1;
        if (nums.length == 1) {
            return 0;
        }
        if (nums.length == 2) {
            return nums[0] > nums[1] ? 0 : 1;
        }
        int lo = 0, hi = nums.length - 1;
        int mi = lo + (hi - lo) / 2;
        // 没有碰到边界情况
        while (mi != 0 && mi != nums.length - 1) {
            if (nums[mi] > nums[mi + 1] && nums[mi] > nums[mi - 1]) {
                return mi;
            } else {
                if (nums[mi + 1] > nums[mi - 1])
                    lo = mi + 1;
                else
                    hi = mi - 1;
            }
            mi = lo + (hi - lo) / 2;
        }
        // 边界情况特殊判断
        if (mi == 0) {
            return nums[mi] > nums[mi + 1] ? mi : mi + 1;
        } else {
            return nums[mi] > nums[mi - 1] ? mi : mi - 1;
        }
    }

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        return self.helper(0, nums)

    def helper(self, base, nums):
        # print(base,nums)
        if (len(nums) == 0):
            return -1
        if (len(nums) == 1):
            return 0 + base
        if (len(nums) == 2):
            return 0 + base if nums[0] > nums[1] else 1 + base
        lo, hi = 0, len(nums) - 1
        mi = (hi - lo) // 2
        if (nums[mi] > nums[mi - 1] and nums[mi] > nums[mi + 1]):
            return mi + base
        if (nums[mi - 1] > nums[mi + 1]):
            return self.helper(lo + base, nums[lo:mi])
        else:
            return self.helper(mi + 1 + base, nums[mi + 1:hi + 1])

2D finding

public static int func1(int a[][]) {
//      变化的维度
        int dx[] = {0, -1, 0, 1};
        int dy[] = {-1, 0, 1, 0};

        // 依次遍历矩阵中的元素，找到第一个局部最小的元素
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                boolean flag = true;
                for (int k = 0; k < 4; k++) {
                    int tx = i + dx[k];
                    int ty = j + dy[k];
                    if (tx < 0 || ty < 0 || tx >= a.length || ty >= a.length) {
                        continue;
                    }
                    if (a[tx][ty] <= a[i][j]) {
                        flag = false;
                        break;
                    }
                }
                if (flag) return a[i][j];
            }
        }
//      上面的遍历始终会返回一个数，这里的return是为了通过编译
        return -1;
    }

public static int func2(int a[][]) {
        if (a == null || a.length == 0 || (a.length == 1 && a[0].length == 0))
            throw new Error("矩阵不能为空");
        // 矩阵长度
        int N = a.length;
        int lo = 0, hi = N * N - 1;

        int dx[] = {0, -1, 0, 1};
        int dy[] = {-1, 0, 1, 0};

        while (true) {
            // 二分的mid元素
            int mi = lo + (hi - lo) / 2;
            // mid元素对应矩阵中的下标
            int x = mi / N, y = mi % N;
            int min = a[x][y];
            // 如果当前a[x][y]不满足条件，则从更小的元素开始二分
            int nx = x, ny = y;
            boolean flag = true;
            for (int k = 0; k < 4; k++) {
                int tx = x + dx[k];
                int ty = y + dy[k];
                if (tx < 0 || ty < 0 || tx >= a.length || ty >= a.length) {
                    continue;
                }
                if (a[tx][ty] < a[x][y]) {
                    flag = false;
                }
                // 标记周围元素中最小的
                if (a[tx][ty] < min) {
                    min = a[ty][ty];
                    nx = tx;
                    ny = ty;
                }
            }
            if (flag) return a[x][y];
            int min_ind = nx * N + ny;
            if (min_ind > mi)
                lo = min_ind;
            else
                hi = min_ind;
        }
    }

        int A[][] = {{5, 7, 3}, {8, 4, 1}, {2, 9, 10}};
        int B[][] = {{15, 4, 7, 9}, {6, 13, 8, 99}, {14, 21, 3, 17}, {16, 24, 2, 11}};
        int C[][] = {{}};
        int D[][] = {{1}};
        System.out.println(func1(A));
        System.out.println(func1(B));
        System.out.println(func1(C));
        System.out.println(func1(D));
        System.out.println("===");
        System.out.println(func2(A));
        System.out.println(func2(B));
        System.out.println(func2(C));
        System.out.println(func2(D));

/*
5
4
-1
1
===
2
4
Exception in thread "main" java.lang.Error: 矩阵不能为空
	at ch01.part4.ex_1_4_19.func2(ex_1_4_19.java:41)
	at ch01.part4.ex_1_4_19.main(ex_1_4_19.java:97)
*/

MIT讲义

1. 选择中间的列作为起点，找到该列最大的元素，位于i,j

2. 比较

3. 如果比大，那么就选择左列然后重复上述步骤

4. 如果比大，那么就选择右列然后重复上述步骤

5. 如果最大，那么它就是答案

//  寻找局部最大
    public static int func3(int a[][]) {
        int N = a.length;
        int y = N / 2;
        while (true) {
            int max = 0;
            int x = 0;
            // 寻找该列最大元素
            for (int i = 0; i < a.length; i++) {
                if (a[i][y] > max) {
                    x = i;
                    max = a[i][y];
                }
            }
            if (y > 0 && a[x][y] < a[x][y - 1])
                y = y - 1;
            else if (y < a.length - 1 && a[x][y] < a[x][y + 1])
                y = y + 1;
            else
                return a[x][y];
        }

总结

参考

延伸