package y2019.Algorithm.array.medium;

/**

 * @ProjectName: cutter-point

 * @Package: y2019.Algorithm.array.medium

 * @ClassName: FindPeakElement

 * @Author: xiaof

 * @Description: TODO 162. Find Peak Element

 * A peak element is an element that is greater than its neighbors.

 * Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

 * The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

 * You may imagine that nums[-1] = nums[n] = -∞.

 *

 * 峰值元素是指其值大于左右相邻值的元素。

 * 给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。

 * 数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

 * 你可以假设 nums[-1] = nums[n] = -∞。

 *

 * 来源：力扣（LeetCode）

 * 链接：https://leetcode-cn.com/problems/find-peak-element

 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 *

 * Input: nums = [1,2,3,1]

 * Output: 2

 * Explanation: 3 is a peak element and your function should return the index number 2.

 *

 * @Date: 2019/7/24 8:57

 * @Version: 1.0

 */

public class FindPeakElement {

    public int solution(int[] nums) {

        if(nums == null || nums.length <= 0) {

            return -1;

        }

        if(nums.length == 1) {

            return 0;

        }

        //二分查找局部最大值

        int l  = 0, r = nums.length - 1;

        int res = -1;

        while (l <= r) {

            int mid = (l + r) / 2;

            //判断mid是否锋值,比之前的数据和之后的数据都要大，如果是边缘数据，那么就只要比较一边就行

            int left = (mid - 1) < 0 ? Integer.MIN_VALUE : nums[mid - 1];

            int right = (mid + 1) >= nums.length ? Integer.MIN_VALUE : nums[mid + 1];

            if(nums[mid] > left && nums[mid] > right) {

                res = mid;

                return res;

            } else if (left > nums[mid]) {

                //左边比较大，我们往左边靠

                r = mid - 1;

            } else {

                l = mid + 1;

            }

        }

        return res;

    }

}

package y2019.Algorithm.array.medium;

/**

 * @ProjectName: cutter-point

 * @Package: y2019.Algorithm.array.medium

 * @ClassName: SetZeroes

 * @Author: xiaof

 * @Description:  TODO 73. Set Matrix Zeroes

 * Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

 *

 * Input:

 * [

 *   [1,1,1],

 *   [1,0,1],

 *   [1,1,1]

 * ]

 * Output:

 * [

 *   [1,0,1],

 *   [0,0,0],

 *   [1,0,1]

 * ]

 *

 * A straight forward solution using O(mn) space is probably a bad idea.

 * A simple improvement uses O(m + n) space, but still not the best solution.

 * Could you devise a constant space solution?

 *

 * @Date: 2019/7/24 9:44

 * @Version: 1.0

 */

public class SetZeroes {

    public void solution(int[][] matrix) {

        //这题要求空间复杂度小于O（m+n）

        //如果是这个要求的话，双循环直接再原来的矩阵中操作

        //1.首先吧矩阵的边上的位置应该为0的设置为0

        int c = 1;

        for(int i = 0; i < matrix.length; ++i) {

            if(matrix[i][0] == 0) c = 0; //如果本身这个位置边上就是0

            for(int j = 1; j < matrix[i].length; ++j) {

                //设置边为0

                if(matrix[i][j] == 0) {

                    matrix[i][0] = matrix[0][j] = 0;

                }

            }

        }

        //2.再次遍历矩阵，只要这个i,j对应的值的i,0或者0，j为0，那么就设置为0

        //因为设置为0的是上面和左边，那么我们从右下开始遍历

        for(int i = matrix.length - 1; i >= 0; --i) {

            for(int j = matrix[i].length - 1; j >= 1; --j) { //第一列不用遍历，因为已经修改过了

                //设置边为0

                if(matrix[i][0] == 0 || matrix[0][j] == 0) {

                    matrix[i][j] = 0;

                }

            }

            //最后一列单独判断,避免重复吧变化了之后的数据再次操作

            if(c == 0) {

                //c标识这个列上本身存在0

                matrix[i][0] = 0;

            }

        }

    }

}