数组的常见算法一

注: 本文来自尚硅谷-宋红康仅用来学习备份

6.1 数值型数组特征值统计

• 这里的特征值涉及到：平均值、最大值、最小值、总和等

**举例1：**数组统计：求总和、均值

public class TestArrayElementSum {public static void main(String[] args) {int[] arr = {4,5,6,1,9};//求总和、均值int sum = 0;//因为0加上任何数都不影响结果for(int i=0; i<arr.length; i++){sum += arr[i];}double avg = (double)sum/arr.length;System.out.println("sum = " + sum);System.out.println("avg = " + avg);}
}

**举例2：**求数组元素的总乘积

public class TestArrayElementMul {public static void main(String[] args) {int[] arr = {4,5,6,1,9};//求总乘积long result = 1;//因为1乘以任何数都不影响结果for(int i=0; i<arr.length; i++){result *= arr[i];}System.out.println("result = " + result);}
}

**举例3：**求数组元素中偶数的个数

public class TestArrayElementEvenCount {public static void main(String[] args) {int[] arr = {4,5,6,1,9};//统计偶数个数int evenCount = 0;for(int i=0; i<arr.length; i++){if(arr[i]%2==0){evenCount++;}}System.out.println("evenCount = " + evenCount);}
}

**举例4：**求数组元素的最大值

public class TestArrayMax {public static void main(String[] args) {int[] arr = {4,5,6,1,9};//找最大值int max = arr[0];for(int i=1; i<arr.length; i++){//此处i从1开始，是max不需要与arr[0]再比较一次了if(arr[i] > max){max = arr[i];}}System.out.println("max = " + max);}
}

**举例5：**找最值及其第一次出现的下标

public class TestMaxIndex {public static void main(String[] args) {int[] arr = {4,5,6,1,9};//找最大值以及第一个最大值下标int max = arr[0];int index = 0;for(int i=1; i<arr.length; i++){if(arr[i] > max){max = arr[i];index = i;}}System.out.println("max = " + max);System.out.println("index = " + index);}
}

**举例6：**找最值及其所有最值的下标

public class Test13AllMaxIndex {public static void main(String[] args) {int[] arr = {4,5,6,1,9,9,3};//找最大值int max = arr[0];for(int i=1; i<arr.length; i++){if(arr[i] > max){max = arr[i];}}System.out.println("最大值是：" + max);System.out.print("最大值的下标有：");//遍历数组，看哪些元素和最大值是一样的for(int i=0; i<arr.length; i++){if(max == arr[i]){System.out.print(i+"\t");}}System.out.println();}
}

优化

public class Test13AllMaxIndex2 {public static void main(String[] args) {int[] arr = {4,5,6,1,9,9,3};//找最大值int max = arr[0];String index = "0";for(int i=1; i<arr.length; i++){if(arr[i] > max){max = arr[i];index = i + "";}else if(arr[i] == max){index += "," + i;}}System.out.println("最大值是" + max);System.out.println("最大值的下标是[" + index+"]");}
}

**举例7(难)：**输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如：输入的数组为1, -2, 3, -10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。

public class Test5 {public static void main(String[] args) {int[] arr = new int[]{1, -2, 3, 10, -4, 7, 2, -5};int i = getGreatestSum(arr);System.out.println(i);}public static int getGreatestSum(int[] arr){int greatestSum = 0;if(arr == null || arr.length == 0){return 0;}int temp = greatestSum;for(int i = 0;i < arr.length;i++){temp += arr[i];if(temp < 0){temp = 0;}if(temp > greatestSum){greatestSum = temp;}}if(greatestSum == 0){greatestSum = arr[0];for(int i = 1;i < arr.length;i++){if(greatestSum < arr[i]){greatestSum = arr[i];}}}return greatestSum;}
}

举例8：评委打分

分析以下需求，并用代码实现：

（1）在编程竞赛中，有10位评委为参赛的选手打分，分数分别为：5，4，6，8，9，0，1，2，7，3

（2）求选手的最后得分（去掉一个最高分和一个最低分后其余8位评委打分的平均值）

/*** @author 尚硅谷-宋红康* @create 10:03*/
public class ArrayExer {public static void main(String[] args) {int[] scores = {5,4,6,8,9,0,1,2,7,3};int max = scores[0];int min = scores[0];int sum = 0;for(int i = 0;i < scores.length;i++){if(max < scores[i]){max = scores[i];}if(min > scores[i]){min = scores[i];}sum += scores[i];}double avg = (double)(sum - max - min) / (scores.length - 2);System.out.println("选手去掉最高分和最低分之后的平均分为：" + avg);}
}

6.2 数组元素的赋值与数组复制

**举例1：**杨辉三角

案例：使用二维数组打印一个 10 行杨辉三角。

提示：

1. 第一行有 1 个元素, 第 n 行有 n 个元素
2. 每一行的第一个元素和最后一个元素都是 1
3. 从第三行开始, 对于非第一个元素和最后一个元素的元素。即：
   yanghui[i][j] = yanghui[i-1][j-1] + yanghui[i-1][j];

public class YangHuiTest {public static void main(String[] args) {//1. 创建二维数组int[][] yangHui = new int[10][];//2.使用循环结构，初始化外层数组元素for(int i = 0;i < yangHui.length;i++){yangHui[i] = new int[i + 1];//3. 给数组的元素赋值//3.1 给数组每行的首末元素赋值为1yangHui[i][0] = yangHui[i][i] = 1;//3.2 给数组每行的非首末元素赋值//if(i >= 2){for(int j = 1;j < yangHui[i].length - 1;j++){ //j从每行的第2个元素开始，到倒数第2个元素结束yangHui[i][j] = yangHui[i - 1][j] + yangHui[i - 1][j - 1];}//}}//遍历二维数组for (int i = 0; i < yangHui.length; i++) {for (int j = 0; j < yangHui[i].length; j++) {System.out.print(yangHui[i][j] + "\t");}System.out.println();}}
}

**举例2：**使用简单数组

(1)创建一个名为ArrayTest的类，在main()方法中声明array1和array2两个变量，他们是int[]类型的数组。

(2)使用大括号{}，把array1初始化为8个素数：2,3,5,7,11,13,17,19。

(3)显示array1的内容。

(4)赋值array2变量等于array1，修改array2中的偶索引元素，使其等于索引值(如array[0]=0,array[2]=2)。打印出array1。 array2 = array1;

**思考：**array1和array2是什么关系？

**拓展：**修改题目，实现array2对array1数组的复制

**举例3：**一个数组，让数组的每个元素去除第一个元素，得到的商作为被除数所在位置的新值。

public class Test3 {public static void main(String[] args) {int[] arr = new int[]{12,43,65,3,-8,64,2};//		for(int i = 0;i < arr.length;i++){
//			arr[i] = arr[i] / arr[0];
//		}for(int i = arr.length -1;i >= 0;i--){arr[i] = arr[i] / arr[0];}//遍历arrfor(int i = 0;i < arr.length;i++){System.out.print(arr[i] + " ");}}
}

**举例4：**创建一个长度为6的int型数组，要求数组元素的值都在1-30之间，且是随机赋值。同时，要求元素的值各不相同。

public class Test4 {// 5-67 Math.random() * 63 + 5;@Testpublic void test1() {int[] arr = new int[6];for (int i = 0; i < arr.length; i++) {// [0,1) [0,30) [1,31)arr[i] = (int) (Math.random() * 30) + 1;boolean flag = false;while (true) {for (int j = 0; j < i; j++) {if (arr[i] == arr[j]) {flag = true;break;}}if (flag) {arr[i] = (int) (Math.random() * 30) + 1;flag = false;continue;}break;}}for (int i = 0; i < arr.length; i++) {System.out.println(arr[i]);}}//更优的方法@Testpublic void test2(){int[] arr = new int[6];for (int i = 0; i < arr.length; i++) {// [0,1) [0,30) [1,31)arr[i] = (int) (Math.random() * 30) + 1;for (int j = 0; j < i; j++) {if (arr[i] == arr[j]) {i--;break;}}}for (int i = 0; i < arr.length; i++) {System.out.println(arr[i]);}}
}

**举例5：**扑克牌

案例：遍历扑克牌

遍历扑克牌，效果如图所示：

提示：使用两个字符串数组，分别保存花色和点数，再用一个字符串数组保存最后的扑克牌。
String[] hua = {“黑桃”,“红桃”,“梅花”,“方片”};
String[] dian = {“A”,“2”,“3”,“4”,“5”,“6”,“7”,“8”,“9”,“10”,“J”,“Q”,“K”};

package com.atguigu3.common_algorithm.exer5;/*** @author 尚硅谷-宋红康* @create 17:16*/
public class ArrayExer05 {public static void main(String[] args) {String[] hua = {"黑桃","红桃","梅花","方片"};String[] dian = {"A","2","3","4","5","6","7","8","9","10","J","Q","K"};String[] pai = new String[hua.length * dian.length];int k = 0;for(int i = 0;i < hua.length;i++){for(int j = 0;j < dian.length;j++){pai[k++] = hua[i] + dian[j];}}for (int i = 0; i < pai.length; i++) {System.out.print(pai[i] + "  ");if(i % 13 == 12){System.out.println();}}}
}

拓展：在上述基础上，增加大王、小王。

**举例6：**回形数

从键盘输入一个整数（1~20） ，则以该数字为矩阵的大小，把1,2,3…n*n 的数字按照顺时针螺旋的形式填入其中。

例如： 输入数字2，则程序输出：
1 2
4 3

输入数字3，则程序输出：
1 2 3
8 9 4
7 6 5
输入数字4， 则程序输出：
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7

//方式1
public class RectangleTest {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);System.out.println("输入一个数字");int len = scanner.nextInt();int[][] arr = new int[len][len];int s = len * len;/** k = 1:向右* k = 2:向下* k = 3:向左* k = 4:向上*/int k = 1;int i = 0,j = 0;for(int m = 1;m <= s;m++){if(k == 1){if(j < len && arr[i][j] == 0){arr[i][j++] = m;}else{k = 2;i++;  j--;m--;}}else if(k == 2){if(i < len && arr[i][j] == 0){arr[i++][j] = m;}else{k = 3;i--;j--;m--;}}else if(k == 3){if(j >= 0 && arr[i][j] == 0){arr[i][j--] = m;}else{k = 4;i--;j++;m--;}}else if(k == 4){if(i >= 0 && arr[i][j] == 0){arr[i--][j] = m;}else{k = 1;i++;j++;m--;}}}//遍历for(int m = 0;m < arr.length;m++){for(int n = 0;n < arr[m].length;n++){System.out.print(arr[m][n] + "\t");}System.out.println();}}
}

//方式2
/*01 02 03 04 05 06 07 24 25 26 27 28 29 08 23 40 41 42 43 30 09 22 39 48 49 44 31 10 21 38 47 46 45 32 11 20 37 36 35 34 33 12 19 18 17 16 15 14 13 */
public class RectangleTest1 {public static void main(String[] args) {int n = 7;int[][] arr = new int[n][n];int count = 0; //要显示的数据int maxX = n-1; //x轴的最大下标int maxY = n-1; //Y轴的最大下标int minX = 0; //x轴的最小下标int minY = 0; //Y轴的最小下标while(minX<=maxX) {for(int x=minX;x<=maxX;x++) {arr[minY][x] = ++count;}minY++;for(int y=minY;y<=maxY;y++) {arr[y][maxX] = ++count;}maxX--;for(int x=maxX;x>=minX;x--) {arr[maxY][x] = ++count;}maxY--;for(int y=maxY;y>=minY;y--) {arr[y][minX] = ++count;}minX++;}for(int i=0;i<arr.length;i++) {for(int j=0;j<arr.length;j++) {String space = (arr[i][j]+"").length()==1 ? "0":"";System.out.print(space+arr[i][j]+" ");}System.out.println();}}
}

6.3 数组元素的反转

**实现思想：**数组对称位置的元素互换。

public class TestArrayReverse1 {public static void main(String[] args) {int[] arr = {1,2,3,4,5};System.out.println("反转之前：");for (int i = 0; i < arr.length; i++) {System.out.println(arr[i]);}//反转/*思路：首尾对应位置的元素交换（1）确定交换几次次数 = 数组.length / 2（2）谁和谁交换for(int i=0; i<次数; i++){int temp = arr[i];arr[i] = arr[arr.length-1-i];arr[arr.length-1-i] = temp;}*/for(int i=0; i<arr.length/2; i++){int temp = arr[i];arr[i] = arr[arr.length-1-i];arr[arr.length-1-i] = temp;}System.out.println("反转之后：");for (int i = 0; i < arr.length; i++) {System.out.println(arr[i]);}}}

或

public class TestArrayReverse2 {public static void main(String[] args) {int[] arr = {1,2,3,4,5};System.out.println("反转之前：");for (int i = 0; i < arr.length; i++) {System.out.println(arr[i]);}//反转//左右对称位置交换for(int left=0,right=arr.length-1; left<right; left++,right--){//首  与  尾交换int temp = arr[left];arr[left] = arr[right];arr[right] = temp;}System.out.println("反转之后：");for (int i = 0; i < arr.length; i++) {System.out.println(arr[i]);}}
}

6.4 数组的扩容与缩容

数组的扩容

题目：现有数组 int[] arr = new int[]{1,2,3,4,5}; ，现将数组长度扩容1倍，并将10,20,30三个数据添加到arr数组中，如何操作？

public class ArrTest1 {public static void main(String[] args) {int[] arr = new int[]{1,2,3,4,5};int[] newArr = new int[arr.length << 1];for(int i = 0;i < arr.length;i++){newArr[i] = arr[i];}newArr[arr.length] = 10;newArr[arr.length + 1] = 20;newArr[arr.length + 2] = 30;arr = newArr;//遍历arrfor (int i = 0; i < arr.length; i++) {System.out.println(arr[i]);}}
}

数组的缩容

题目：现有数组 int[] arr={1,2,3,4,5,6,7}。现需删除数组中索引为4的元素。

public class ArrTest2 {public static void main(String[] args) {int[] arr = {1, 2, 3, 4, 5, 6, 7};//删除数组中索引为4的元素int delIndex = 4;//方案1：/*//创建新数组int[] newArr = new int[arr.length - 1];for (int i = 0; i < delIndex; i++) {newArr[i] = arr[i];}for (int i = delIndex + 1; i < arr.length; i++) {newArr[i - 1] = arr[i];}arr = newArr;for (int i = 0; i < arr.length; i++) {System.out.println(arr[i]);}*///方案2：for (int i = delIndex; i < arr.length - 1; i++) {arr[i] = arr[i + 1];}arr[arr.length - 1] = 0;for (int i = 0; i < arr.length; i++) {System.out.println(arr[i]);}}
}