数组中这些常用算法你掌握了吗？

站长

2023年07月25日 12:29 · 阅读数 11

今天继续Java系列，上篇讲了Java数组，今天来看下数组的常见算法。

算法概述

算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷不适合于某个问题，那么执行这个算法将不会解决问题。

算法效率的两个重要衡量指标是时间复杂度和空间复杂度。

时间复杂度

时间复杂度是指执行算法所需要的计算工作量，可以通过分析算法中的循环次数来得到。

常见的算法时间复杂度由小到大依次为：O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)。

注：经常将以2为底n的对数简写成logn。

空间复杂度

空间复杂度是指执行这个算法所需要的内存空间，它也是问题规模n的函数，可以通过分析算法中的变量个数来得到。

时间复杂度和空间复杂度都是用O表示的，例如O(n)、O(n^2) 等等。

常见算法

数组特征值统计

这里的特征值是指：平均值、最大值、最小值、总和等。

下面举个例子：找最值及其第一次出现的下标。

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);
    }
}

再来个难点的例子看下：输入一个整形数组，数组里有正数也有负数，数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。

例如：输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。

public class Test {
	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;
	}
}

数组赋值与数组复制

这里看个经典的例子：回形数。从键盘输入一个整数(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-49的回形数：
	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 RectangleTest {
	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();
		}
	}
}