超硬核！躺进BAT以后我总结了出现最多的15道数组题

逃离我推掉我的手 2022-10-23 01:50 145阅读 0赞

> 作为一个硬核作者，绝不和你扯废话，干货无套路送你

# 题目一： #

给定一个数组arr，求出需要排序的最短子数组长度

要求：

时间o(n),空间o(1)

思路：

有序的数组中，任意一个数字，一定小于左边的数大于右边的数。

我们找到的需要排序的子数组，显然是比右边最小的值大，或比左边最大的值小。

我们初始化变量noMinindex=-1;从右往左遍历，记录经过的最小值为min，若当前数大于min，说明，如果要有序，min一定要放 在当前数左边，我们更新noMinindex。

也就是说，我们的noMinindex是负责记录最左边出现这种情况的位置。我们反方向处理出noMaxindex

他们组成的区间就是最短需要排序的部分了

public class MinLengthForSort {
    	public static int getMinLength(int[] arr) {
    		if (arr == null || arr.length < 2) {
    			return 0;
    		}
    		int min = arr[arr.length - 1];
    		int noMinIndex = -1;
    		for (int i = arr.length - 2; i != -1; i--) {
    			if (arr[i] > min) {
    				noMinIndex = i;
    			} else {
    				min = Math.min(min, arr[i]);
    			}
    		}
    		if (noMinIndex == -1) {
    			return 0;
    		}
    		int max = arr[0];
    		int noMaxIndex = -1;
    		for (int i = 1; i != arr.length; i++) {
    			if (arr[i] < max) {
    				noMaxIndex = i;
    			} else {
    				max = Math.max(max, arr[i]);
    			}
    		}
    		return noMaxIndex - noMinIndex + 1;
    	}
    	public static void main(String[] args) {
    		int[] arr = { 1, 2, 4, 7, 10, 11, 7, 12, 6, 7, 16, 18, 19 };
    		System.out.println(getMinLength(arr));
    
    	}
    
    }

# 题目二： #

给定一个数组，找出出现次数超过一半的数字

蠢思路：排序找中间

思路：

DP：扫一遍一个变量count记录解出现的次数，是当前解就++，否则--，count为负就换掉当前解。（解释：想象解全都挨在 一起（前面），count先达到最大，然后减为1或0，而其他数字先出现，可能会使正确解的count减为负数，但都会使正确解 在后面更多，从而保证了结束时肯定为正确解）

int main()
    {
        int n;//个数
        scanf("%d",&n);
        int temp,k,count=0;
        while(n--)
        {
            scanf("%d",&temp);
            if(temp==k)count++;
            else
            {
                count--;
                if(count<0){count=0;k=temp;}
            }
        }
        printf("%d\n",k);
    }

# 题目三： #

给定一个有N×M的整型矩阵matrix和一个整数K，matrix的每一行和每一列都是排好序的。实现一个函数，判断K是否在matrix中。

例如：

0 1 2 5

2 3 4 7

4 4 4 8

5 7 7 9

如果K为7，返回true，如果K为6，返回false

要求：

时间复杂度为O(N+M)，额外空间复杂度为O(1)。

思路：

1.从矩阵最右上角的数开始寻找（row=0,col=M-1）。

2.比较当前数matrix\[row\]\[col\]与K的关系：

如果与K相等，说明已找到，直接返回true

如果比K大，因为矩阵每一列都已排好序，所以在当前数所在的列中，处于当前数下方的数都会比K大，则没有必要继续在第col列上寻找，令col=col-1，重复步骤2.

如果比K小，因为矩阵每一行都已排好序，所以在当前数所在的行中，处于当前数左方的数都会比K小，则没有必要继续在第row行上寻找，令row=row+1,重复步骤2.

3.如果找到越界都没有发现与K相等的数，则返回false。

或者可以从矩阵的最左下角的数开始寻找（row=N-1,col=0），具体过程类似。

代码：

/**
     * 在行列都排好序的矩阵中找数
     */
    public class IsContains {
        public boolean isContains(int[][] matrix, int K) {
            int row = 0;
            int col = matrix[0].length - 1;
            while (row < matrix.length && col > -1) {
                if (matrix[row][col] == K) {
                    return true;
                } else if (matrix[row][col] > K) {
                    col--;
                } else {
                    row++;
                }
            }
            return false;
        }
    }

# 题目四：转圈打印矩阵 #

题目：

给定一个整型矩阵matrix，请按照转圈的方式打印它。例如：1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,打印结果为：1,2,3,4,5,12,16,15,14,13,9,5,6,7,11,10

要求：

额外空间复杂度为O（1）

思路：

矩阵分圈处理。在矩阵中用左上角的坐标（tR,tC）和右下角的坐标（dR,dC）就可以表示一个矩阵，比如，题目中的矩阵，当（tR,tC）=(0,0)，（dR,dC）=(3,3)时，表示的子矩阵就是整个矩阵，那么这个子矩阵的最外层的部分如下：

1 2 3 4

5 8

9 12

13 14 15 16

如果能把这个子矩阵的外层转圈打印出来，那么在(tR,tC)=(0,0)、(dR,dC)=(3,3)时，打印结果为：1,2,3,4,8,12,16,15,14,13,9,5。接下来令tR和tC加1，即(tR,tC)=(1,1)，令dR和dC减1，即(dR,dC)=(2,2)，此时表示的子矩阵如下：

6 7

10 11

再把这个子矩阵转圈打印出来，结果为：6,7,11,10。把tR和tC加1，即(tR,tC)=(2,2)，令dR和dC减1，即(dR,dC)=(1,1)。如果发现左上角坐标跑到右下角坐标的右方或下方，整个过程就停止。已经打印的所有结果连接起来就是我们要求的打印结果。

代码：

/**
     * 转圈打印矩阵
     */
    public class PrintMatrixSpiralOrder {
        public void spiralOrderPrint(int[][] matrix) {
            int tR = 0;
            int tC = 0;
            int dR = matrix.length - 1;
            int dC = matrix[0].length - 1;
            while (tR <= dR && tC <= dC) {
                printEdge(matrix, tR++, tC++, dR--, dC--);
            }
        }
     
        //转圈打印一个子矩阵的外层，左上角点（tR,tC），右下角点（dR,dC）
        private void printEdge(int[][] matrix, int tR, int tC, int dR, int dC) {
            if (tR == dR) {//子矩阵只有一行时
                for (int i = tC; i <= dC; i++) {
                    System.out.print(matrix[tR][i] + " ");
                }
            } else if (tC == dC) {//子矩阵只有一列时
                for (int i = tR; i <= dR; i++) {
                    System.out.print(matrix[i][tC] + " ");
                }
            } else {//一般情况
                int curCol = tC;
                int curRow = tR;
                while (curCol != dC) {//从左向右
                    System.out.print(matrix[tR][curCol] + " ");
                    curCol++;
                }
                while (curRow != dR) {//从上到下
                    System.out.print(matrix[curRow][dC] + " ");
                    curRow++;
                }
                while (curCol != tC) {//从右到左
                    System.out.print(matrix[dR][curCol] + " ");
                    curCol--;
                }
                while (curRow != tR) {//从下到上
                    System.out.print(matrix[curRow][tC] + " ");
                    curRow--;
                }
            }
        }
    }

#    题目五：将正方形矩阵顺时针转动90° #

题目：

给定一个N×N的矩阵matrix，把这个矩阵调整成顺时针转动90°后的形式。

例如：

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16

顺时针转动90°后为：

13 9 5 1

14 10 6 2

15 11 7 3

16 12 8 4

要求：

额外空间复杂度为O(1).

思路：

仍然使用分圈处理的方式，

在矩阵中用左上角的坐标（tR,tC）和右下角的坐标（dR,dC）就可以表示一个矩阵，比如，题目中的矩阵，当（tR,tC）=(0,0)，（dR,dC）=(3,3)时，表示的子矩阵就是整个矩阵，那么这个子矩阵的最外层的部分如下：

1 2 3 4

5 8

9 12

13 14 15 16

在这个外圈中，1,4,16,13为一组，然后让1占据4的位置，4占据16的位置，16占据13的位置，13占据1的位置，一组就调整完了。然后2,8,15,9为一组，继续占据调整的过程，最后3,12,14,5为一组，继续占据调整的过程。然后(tR,tC)=(0,0)、(dR,dC)=(3,3)的子矩阵外层就调整完毕，接下来令tR和tC加1，即(tR,tC)=(1,1)，令dR和dC减1，即（dR,dC）=(2,2)，此时表示的子矩阵如下：

6 7

10 11

这个外层只有一组，就是6,7,11,10，占据调整之后即可。所以，如果子矩阵的大小是M×M，一共就有M-1组，分别进行占据调整即可。

代码：

/**
     * 将正方形矩阵顺时针旋转90°
     */
    public class RotateMatrix {
        public static void rotate(int[][] matrix) {
            int tR = 0;
            int tC = 0;
            int dR = matrix.length - 1;
            int dC = matrix[0].length - 1;
            while (tR < dR) {
                rotateEdge(matrix, tR++, tC++, dR--, dC--);
            }
        }
     
        private static void rotateEdge(int[][] matrix, int tR, int tC, int dR, int dC) {
            int times = dC - tC;//times就是总的组数
            int temp = 0;
            for (int i = 0; i != times; i++) {//一次循环就是一组占据调整
                temp = matrix[tR][tC + i];
                matrix[tR][tC + i] = matrix[dR - i][tC];
                matrix[dR - i][tC] = matrix[dR][dC - i];
                matrix[dR][dC - i] = matrix[tR - i][dC];
                matrix[tR - i][dC] = temp;
            }
        }
    }

#    题目六：“之”字形打印矩阵 #

题目：

给定一个矩阵matrix，按照“之”字形的方式打印矩阵，例如：

1 2 3 4

5 6 7 8

9 10 11 12

“之”字形打印的结果为：1,2,5,9,6,3,4,7,10,11,8,12

要求：

额外空间复杂度为O（1）

思路;

上坐标（tR,tC）初始化为（0,0）,先沿着矩阵第一行移动（tC++），当到达第一行最右边的元素后，在沿着矩阵最后一列移动（tR++）。  
下坐标（dR,dC）初始为（0,0）,先沿着矩阵第一列移动（dR++），当到达第一列最下边的元素时，再沿着矩阵最后一行移动（dC++）。  
上坐标与下坐标同步移动，每次移动后的上坐标与下坐标的连线就是矩阵中的一条斜线，打印斜线上的元素即可。  
如果上次斜线是从左下向右上打印的，这次一定是从右上向左下打印，反之亦然。总之，可以把打印的方向用boolean值表示，每次取反即可。  
代码：

/**
     * 之字形打印矩阵
     */
    public class PrintMatrixZigZag {
        public static void printMatrixZigZag(int[][] matrix) {
            int tR = 0;
            int tC = 0;
            int dR = 0;
            int dC = 0;
            int endRow = matrix.length - 1;
            int endCol = matrix[0].length - 1;
            boolean fromUp = false;
            while (tR != endRow + 1) {
                printLevel(matrix, tR, tC, dR, dC, fromUp);
                tR = tC == endCol ? tR + 1 : tR;
                tC = tC == endCol ? tC : tC + 1;
                dR = dR == endRow ? dR : dR + 1;
                dC = dR == endRow ? dC + 1 : dC;
                fromUp = !fromUp;
            }
            System.out.println();
        }
     
        private static void printLevel(int[][] matrix, int tR, int tC, int dR, int dC, boolean fromUp) {
            if (fromUp) {
                while (tR != dR + 1) {//从左下到右上
                    System.out.print(matrix[tR++][tC--] + " ");
                }
            } else {
                while (dR != tR - 1) {//从右上到左下
                    System.out.print(matrix[dR--][dC++] + " ");
                }
            }
        }
    }

# 题目七 #

给定一个长度为N的整型数组arr，其中有N个互不相等的自然数1~N

请实现arr的排序

但是不要把下标0~N-1位置上的数值通过直接赋值的方式替换成1~N。

要求：时间复杂度为O(N)，额外空间复杂度为O(1)。

思路：从左向右检查，检查到需要换的以后，就直接把它放到该去的位置，然后被换掉的数，位置肯定也不对，继续重复相同的方法，最后肯定会跳回来（原因懒得说了自己想想），然后继续往下检查即可。

public static void sort1(int[] arr) {
    		int tmp = 0;
    		int next = 0;
    		for (int i = 0; i != arr.length; i++) {
    			tmp = arr[i];
    			while (arr[i] != i + 1) {
    				next = arr[tmp - 1];
    				arr[tmp - 1] = tmp;
    				tmp = next;
    			}
    		}
    	}

# 题目八 #

![70][]

本题一般思路：依次查找找到比前后都小的数；或者选出最小数，他肯定是局部最小的；等等

但这些都是O(n)的方法，而用二分可以做到O(logn).

二分思路：

考虑最左和最右的元素：如果arr\[0\]<arr\[1\] return 0; arr\[N-1\]<arr\[N-2\] return N-1;

考虑最中间元素，如果中间元素大于它左边的元素，那么局部最小值就应该在数组的左半部分

如果中间元素小于大于它右边的元素，那么局部最小值就应该在数组的右半部分

中间元素既小于它左边的值又小于它右边的值，那么它就是局部最小

# 题目九 #

给定一个整数数组arr，返回不包含本位置的累乘数组。

比如2 3 1 4返回12 8 24 6

方法一：算出所有数的乘积，每个位置除以自己即可。要注意坑：如果数组中有一个0，那么0这个位置就是其他数的乘积，其他位置全为0；如果有多个0，那么所有位置都是0.

public int[] product1(int[] arr) {
    		if(arr==null || arr.length<2) {
    			return null;
    		}
    		int count=0;//0的个数
    		int all=1;//除0以外的数的乘积
    		for(int i=0;i!=arr.length;i++) {
    			if(arr[i]!=0) {
    				all*=arr[i];
    			}else {
    				count++;
    			}
    		}
    		int[] res=new int[arr.length];
    		if(count==0) {
    			for(int i=0;i!=arr.length;i++) {
    				res[i]=all/res[i];
    			}
    		}else if(count==1) {
    			for(int i=0;i!=arr.length;i++) {
    				if(arr[i]==0) {
    					res[i]=all;
    				}
    			}
    		}
    		return res;
    	}

# 题目十：子数组的最大累加和问题 #

输入一个整形数组，求数组中连续的子数组使其和最大。比如，数组x  
![54e7e781067872cdf72590f519d61f0d.png][]

应该返回 x\[2..6\]的和187.

这四个代码完成的功能都是求最大子数组（注意用词准确，子数组连续，子序列可以不连续）。

1）

for(i = 1; i <= n; i++)
    	scanf("%d", &num[i]);
    ans = num[1]; 
    for(i = 1; i <= n; i++)
    {
    	for(j = i; j <= n; j++) 
    	{
    		s = 0;
    		for(k = i; k <= j; k++)
    			s += num[k];
    		if(s > ans)
    			ans = s;
    	}
    }

分别枚举每一个子数组的起点和终点，也就是i和j，对于每一个起点和终点，对中间部分求和，也就是k循环。显然有n个起点n个终点（去重减半，不影响复杂度），所以子数组数量为O(N^2)，对于每个子数组，我们要遍历一下求和，子数组长度1-n不等，遍历一遍平均O(N)，乘起来O(N^3).（注意可能产生时间更大的错觉）。找出所有子数组中最大的即可。

2）

for(i = 1; i <= n; i++)
    	scanf("%d", &num[i]);
    sum[0] = 0;
    for(i = 1; i <= n; i++) {
    	sum[i] = num[i] + sum[i - 1];
    }
    ans = num[1]; 
    for(i = 1; i <= n; i++) {
    	for(j = i; j <= n; j++) {
    		s = sum[j] - sum[i - 1];
    		if(s > ans) ans = s;
    	}
    }

预处理出每一个以第一个元素开始，第i个元素结尾的子数组和，还是枚举每个起点终点，但是我们求和时直接减就可以了，不用遍历。对于每个子数组，操作为O(1),子数组数量O(N^2),所以总时间O(N^2).

3）

int solve(int left, int right)
    {
    	if(left == right)
    		return num[left];
     
    	mid = (left + right) / 2;
    	lans = solve(left, mid);
    	rans = solve(mid + 1, right);
     
    	sum = 0, lmax = num[mid], rmax = num[mid + 1];
    	for(i = mid; i >= left; i--) {
    		sum += num[i];
    		if(sum > lmax) lmax = sum;
    	}
    	sum = 0;
    	for(i = mid + 1; i <= right; i++) {
    		sum += num[i];
    		if(sum > rmax) rmax = sum;
    	}
     
    	ans = lmax + rmax;
    	if(lans > ans) ans = lans;
    	if(rans > ans) ans = rans;
    	return ans;
    }
     
    int main(void)
    {
    	scanf("%d", &n);
    	for(i = 1; i <= n; i++)
    		scanf("%d", &num[i]);
     
    	printf("%d\n", solve(1, n));
    	return 0;
    }

二分，求左右两边最大子数组，取最大。但是还有一种情况：包含断点的那些子数组也要考虑，请思考那两个那两个循环为什么那么写？最后逻辑为何正确？

4）动态规划入门思想

没有枚举，num\[i\]的含义是以下标i结尾的所有子数组中最大的。

遍历数组，对于第i个元素，它的所有子数组下标范围有\[1,i\],\[2,i\].....\[i-1,i\],还有它自己，我们看i-1个元素，他的子数组为\[1,i-1\],\[2,i-1\].....\[i-1\]。请想num\[i\]的含义，我们求i结尾的，只要把i-1结尾的最大加上i就好了，当然如果i-1结尾最大子数组是负的，i结尾最大子数组就是它本身。

为什么O(N)？时间省在哪里了？我们省掉了许多没必要的计算，计算i时，之前的数组和已经都计算过，朴素算法并没有记录下来，而是重复计算，造成时间浪费。算法优化的过程就是去掉重复计算的过程。

for(i = 1; i <= n; i++)
    	scanf("%d", &num[i]);
     
    num[0] = 0;
    ans = num[1];
    for(i = 1; i <= n; i++) 
    {
    	if(num[i - 1] > 0) 
    		num[i] += num[i - 1];
    	else
    		num[i] += 0;
    	if(num[i] > ans) 
    		ans = num[i];
    }

# 题目十一、子矩阵的最大累加和问题 #

给一个矩阵，请找出一个矩阵中，和最大的子矩阵。

如果大家看懂了上一题的讲解，我给个提示：利用第二个代码和第四个代码思想的结合

解释：

1 2 3 4

\-1 -2 1 2

1 3 -2 1

\-1 -2 -1 -3

如图是前三行整体最大

怎么做呢？

先用第二个代码的思想，我们进行预处理

每个数代表这一列到这个数位置截止，累加和。

1 2 3 4

0 0 4 6

1 3 2 7

0 1 1 4

然后，我们枚举每一列的起点和终点分别为第0，1，2，3行

然后压缩成一维来做

比如求1-3行的这个矩形，我们拿0和3行减一下就行了

0-1，1-2，1-3，4-4=-1，-1，-2，0就是1-3行压缩后的结果

然后按一维dp来做就好

public class SubMatrixMaxSum {
    	public static int maxSum(int[][] m) {
    		if (m == null || m.length == 0 || m[0].length == 0) {
    			return 0;
    		}
    		int max = Integer.MIN_VALUE;
    		int cur = 0;
    		int[] s = null; // 累加数组
    		for (int i = 0; i != m.length; i++) {
    			s = new int[m[0].length];
    			for (int j = i; j != m.length; j++) {
    				cur = 0;
    				for (int k = 0; k != s.length; k++) {
    					s[k] += m[j][k];
    					cur += s[k];
    					max = Math.max(max, cur);
    					cur = cur < 0 ? 0 : cur;
    				}
    			}
    		}
    		return max;
    	}
    
    	public static void main(String[] args) {
    		int[][] matrix = { { -90, 48, 78 }, { 64, -40, 64 }, { -81, -7, 66 } };
    		System.out.println(maxSum(matrix));
    
    	}
    
    }

# 题目十二、子数组的最大累乘积 #

## 题目： ##

给定一个double类型的数组arr，其中的元素可正、可负、可为0。返回子数组累乘的最大乘积。

## 思路： ##

假设以arr\[i-1\]结尾的数组最小累乘积为min，最大累乘积为max，那么以arr\[i\]结尾的数组的最大累乘积可能有三种情况。

*  max\*arr\[i\]//本身乘之前的最大累乘
 *  min\*arr\[i\]//可能是负负得正变成最大的
 *  arr\[i\]//可能就是它本身，比如之前的max小于1

public class SubArrayMaxProduct {
    
    	public static double maxProduct(double[] arr) {
    		if (arr == null || arr.length == 0) {
    			return 0;
    		}
    		double max = arr[0];
    		double min = arr[0];
    		double res = arr[0];
    		double maxEnd = 0;
    		double minEnd = 0;
    		for (int i = 1; i < arr.length; ++i) {
    			maxEnd = max * arr[i];
    			minEnd = min * arr[i];
    			max = Math.max(Math.max(maxEnd, minEnd), arr[i]);
    			min = Math.min(Math.min(maxEnd, minEnd), arr[i]);
    			res = Math.max(res, max);
    		}
    		return res;
    	}
    
    	public static void main(String[] args) {
    		double[] arr = { -2.5, 4, 0, 3, 0.5, 8, -1 };
    		System.out.println(maxProduct(arr));
    
    	}
    
    }

# 题目十三：调整有序的arr数组，使得左半部分有序且不重复，不用保证右边是否有序。 #

思路：  
u : 左边的最后位置，即0---u为答案  
i : 从u到右遍历  
当arr\[i\]和arr\[u\]不相等时，说明是目前遇到的最大的数，此时调换arr\[u+1\]和arr\[i\]

public static void leftUnique(int[] arr) {
    		if (arr == null || arr.length < 2) {
    			return;
    		}
    		int u = 0;
    		int i = 1;
    		while (i != arr.length) {
    			if (arr[i++] != arr[u]) {
    				swap(arr, ++u, i - 1);
    			}
    		}
    	}

public static void swap(int[] arr, int index1, int index2) {
    		int tmp = arr[index1];
    		arr[index1] = arr[index2];
    		arr[index2] = tmp;
    	}

# 题目十四：数组arr中只有三种值：0，1，2，请排序 #

思路：荷兰国旗问题：[https://blog.csdn.net/hebtu666/article/details/81772701][https_blog.csdn.net_hebtu666_article_details_81772701]

上面的网址介绍了思路和c++实现，本文给出java实现。

public static void sort(int[] arr) {
    		if (arr == null || arr.length < 2) {
    			return;
    		}
    		int left = -1;
    		int index = 0;
    		int right = arr.length;
    		while (index < right) {
    			if (arr[index] == 0) {
    				swap(arr, ++left, index++);
    			} else if (arr[index] == 2) {
    				swap(arr, index, --right);
    			} else {
    				index++;
    			}
    		}
    	}

# 题目十五：数组arr，给定k，请实现比k小的放左边，等于k的放中间，大于k的放右边 #

同样的分三区，只是条件改一下，<k,=k,>k即可。

[70]: /images/20221022/a0aca5c69cc1479ab246bead9e39b90c.png
[54e7e781067872cdf72590f519d61f0d.png]: /images/20221022/92165cc7d68943ebaa773d75b466d4f0.png
[https_blog.csdn.net_hebtu666_article_details_81772701]: https://blog.csdn.net/hebtu666/article/details/81772701