[leetcode question brushing day 35] 1060 Missing element in ordered array, 1901 Find the peak element, 1380 Lucky number in matrix

Day 35

1060 Missing elements in an ordered array

There is an existing one, press Ascending Array of arranged integers nums , Each of these numbers Different from each other .

Give you an integer k , Please find and return the first... From the leftmost side of the array k Missing number .

Method

Because the array is in ascending order , So we can consider using dichotomy to solve this problem , It's easy to know , For subscripts i The elements of , The number of empty elements between it and the first element is nums[i]-nums[0]-i, And what we are looking for is k Missing elements , therefore , We just need to find out The interval between and the first element should not exceed k The maximum subscript of , Then add and k The difference between the , It's the one we want to find k Missing elements .

class Solution {
    
    public int missingElement(int[] nums, int k) {
    
        int l = 0, r = nums.length - 1;
        // Binary search for the largest subscript  
        while (l <= r){
    
            int mid = (l + r) >> 1;
            if (nums[mid] - nums[0] - mid >= k){
    
                r = mid - 1;
            }
            else{
    
                l = mid + 1;
            }
        }
        return nums[r] + k - (nums[r] - nums[0] - r);
    }
}

1901 Find the pinnacle element Ⅱ

One 2D In the grid Peak element That means Strictly greater than Its adjacent grid ( On 、 Next 、 Left 、 Right ) The elements of .

To give you one from 0 Numbered starting Of m x n matrix mat , The values of any two adjacent lattices are inequality . find Any one Peak element mat[i][j] and Return to its position [i,j] .

You can assume that the entire matrix is surrounded by a circle with a value of -1 Lattice of .

It is required that the time complexity must be written O(m log(n)) or O(n log(m)) The algorithm of

Method

According to the characteristics of the elements in the array , Because every number in the array is different , Then there must be such a peak element , And find the peak element , We can use the maximum value of column or row to deal with （ It is equivalent to a dimensionality reduction operation for the element group , We have the maximum value of each row or column to represent that row or column ）. In this way, the problem is transformed into a one-dimensional array , Let's look for a peak .

For in a one-dimensional array , Algorithm for finding peak , We can use the idea of class dichotomy . The specific algorithm is as follows ：

Definition l and r, Make mid=(l+r)/2, Let's compare mid and mid-1, That is to investigate the increase and decrease of this community , If we find that , In this neighborhood , It's incremental , So in mid There must be a peak element on the right of , otherwise mid There must be a peak element on the left . By constantly narrowing the scope of search , Finally find the peak element .

When returning the answer , We just need to be in the column where the answer is , Just find the position of the largest element in the column .

class Solution {
    
    public static int[] dx = {
    0, 0, 1, -1};
    public static int[] dy = {
    1, -1, 0, 0};
    public static int xLength;
    public static int yLength;
    
    public int[] findPeakGrid(int[][] mat) {
    
        xLength = mat.length;
        yLength = mat[0].length;
        int l = 0, r = yLength - 1;
        while (l <= r){
    
            int mid = (l + r) >> 1;
            int curMax = -1;
            int preMax = -1;
            for (int i = 0; i < xLength; ++i){
    
                curMax = Math.max(curMax, mat[i][mid]);
                if (mid - 1 >= 0) preMax = Math.max(preMax, mat[i][mid - 1]);
            }
            if (mid - 1 < 0 || preMax < curMax) l = mid + 1;
            else r = mid - 1;
        }
        int Max = -1, index = -1;
        for (int i = 0; i < xLength; ++i){
    
            if (mat[i][r] > Max) {
    
                Max = mat[i][r];
                index = i;
            }
        }
        return new int[]{
    index ,r};
    }
}

1380 The lucky number in the matrix

To give you one m * n Matrix , The number in the matrix Each are not identical . Please press arbitrarily Return all the lucky numbers in the matrix in order .

Lucky number refers to the elements in the matrix that meet the following two conditions at the same time ：

• The smallest of all elements in the same row

• The largest of all elements in the same column

Method

Because each element in the matrix is different , therefore , There is at most one lucky number in a matrix , Prove slightly .

So we just need to find out the only lucky number .

We maintain the minimum value of each row and the maximum value of each column , And then iterate through the entire array , If you find that the minimum value of the row in a certain position is the same as the maximum value of the column , Then the number in this position is the answer .

class Solution {
    
    public List<Integer> luckyNumbers (int[][] matrix) {
    
        int[] lMax = new int[matrix.length];
        int[] cMax = new int[matrix[0].length];
        for (int i = 0; i < matrix.length; ++i){
    
            lMax[i] = matrix[i][0];
            for (int j = 0; j < matrix[0].length; ++j){
    
                lMax[i] = Math.min(lMax[i], matrix[i][j]);
            }
        }

        for (int j = 0; j < matrix[0].length; ++j){
    
            for (int i = 0; i < matrix.length; ++i){
    
                cMax[j] = Math.max(cMax[j], matrix[i][j]);
            }
        }

        for (int i = 0; i < matrix.length; ++i){
    
            for (int j = 0; j < matrix[0].length; ++j){
    
                if (lMax[i] == cMax[j]) {
    
                    ArrayList<Integer> res = new ArrayList<>();
                    res.add(matrix[i][j]);
                    return res;
                }
            }
        }
        return new ArrayList<Integer>();
    }
}