程序员代码面试指南 [需要排序的最短子数组长度，数组中出现次数超过一半的数字，数组中出现次数超过一半的数字]

需要排序的最短子数组长度

https://www.nowcoder.com/questionTerminal/fccb5d14b44b4b99b34839bdf20588e9?orderByHotValue=1&page=1&onlyReference=false
来源：牛客网

给定一个无序数组arr，求出需要排序的最短子数组的长度，对子数组排序后能使得整个数组有序，即为需要排序的数组。例如：arr=[1,5,3,4,2,6,7]返回4，因为只有[5,3,4,2]需要排序。

输入描述:
输入包含两行，第一行包括一个整数n，代表数组arr长度，第二行n个整数，代表数组arr。
输出描述:
输出一个整数，代表需要排序的最短子数组的长度。

示例1
输入
7
1 5 3 4 2 6 7
输出
4

思路：
初始化变量noMinIndex=-1，从右向左遍历，便利的过程记录右侧出现过的数的最小值，记为min。假设当前数为arr[i]，如果arr[i]>min,说明如果要整体有序，min值必然会移到arr[i]的左边。用noMinIndex记录最左边出现这种情况的位置。如果遍历完成后，noMinIndex的值依然为-1，说明从右向左始终不升序，原数组本来就有序，直接返回0，即完全不需要排序。

接下来从左向右遍历，遍历的过程记录左侧出现过的数的最大值。记为max。假设当前数为arr[i]，如果arr[i]<max,说明如果排序，max的值必然会挪到arr[i]的右边。用变量moMaxindex记录最右边出现这种情况的位置。

遍历完后，arr[noMinIndex…noMaxIndex]是真正需要排序的部分。返回它的长度即可。

import java.util.*;
public class Main{
    public static int getMinLength(int[] array){
        if(array==null||array.length<2){
            return 0;
        }
        int noMinIndex=-1;
        int min=array[array.length-1];
        for(int i=array.length-2;i>-1;i--){
            if(array[i]>min){
                noMinIndex=i;
            }else{
                min=array[i];
            }
        }
        int noMaxIndex=-1;
        int max=array[0];
        for(int i=1;i<array.length;i++){
            if(array[i]<max){
                noMaxIndex=i;
            }else{
                max=array[i];
            }
        }
        return noMaxIndex-noMinIndex+1;
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] array=new int[n];
        for(int i=0;i<n;i++){
            array[i]=sc.nextInt();
        }
        System.out.println(getMinLength(array));
    }
}

题目描述：数组中出现次数超过一半的数字

来源：牛客网
https://www.nowcoder.com/practice/6a406a24b2a14954956a2168e7f42f9d?tpId=101&tqId=33222&tPage=1&rp=1&ru=/ta/programmer-code-interview-guide&qru=/ta/programmer-code-interview-guide/question-ranking

给定一个整型数组arr，请打印其中出现次数大于一半的数，如果没有这样的数，请输出-1。
输入描述:
输入包含两行，第一行包含一个整数n，代表数组长度，第二行包含n个数，代表数组arr。
输出描述:
输出一个整数，代表出现次数大于一半的数，如果没有这样的数，请输出‘-1“。

示例1
输入
5
11 7 5 7 7
输出
7

示例2
输入
4
2 2 3 3
输出
-1

import java.util.*;
 public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] array = new int[n];
        for(int i=0;i<n;i++){
            array[i] = sc.nextInt();
        }
        int result=0;
        int times=0;
        for(int i=0;i<n;i++){
            if(times==0){
                result=array[i];
                times++;
            }else if(result==array[i]){
                times++;
            }else{
                times--;
            }
        }
        int time=0;
        for(int i=0;i<array.length;i++){
            if(array[i]==result){
                time++;
            }
        }
        if(time>n/2){
            System.out.println(result);
        }else{
             System.out.println("-1");
        }
    }
}
*/

数组中出现次数超过一半的数字

https://www.nowcoder.com/practice/b929be9dbbaa489a91afa3fec195c228?tpId=101&tqId=33069&tPage=1&rp=1&ru=/ta/programmer-code-interview-guide&qru=/ta/programmer-code-interview-guide/question-ranking
来源：牛客网

给定一个N \times MN×M的整形矩阵matrix和一个整数K, matrix的每一行和每一列都是排好序的。
实现一个函数，判断K是否在matrix中
[要求]
时间复杂度为O(N+M)O(N+M)，额外空间复杂度为O(1)O(1)。
输入描述:
第一行有三个整数N, M, K
接下来N行，每行M个整数为输入的矩阵
输出描述:
若K存在于矩阵中输出"Yes"，否则输出"No"

示例1
输入
2 4 5
1 2 3 4
2 4 5 6
输出
Yes

示例2
输入
2 4 233
1 2 3 4
2 4 5 6
输出
No

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int M=sc.nextInt();
        int K=sc.nextInt();
        int[][] array=new int[N][M];
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                array[i][j]=sc.nextInt();
            }
        }
        int row=0;
        int col=array[0].length-1;
        while(row<array.length&&col>-1){
            if(K==array[row][col]){
                System.out.println("Yes");
            }else if(K>array[row][col]){
                row++;
            }else{
                col--;
            }
        }
        System.out.println("No");
    }
}