数组

1、数组

1. 说明

• 数组是多个相同类型数据按一定顺序排列的集合。数组是有序的
• 数组是引用数据类型，数组中的元素可以是任何数据类型，但一个数组只能存储被声明类型的数据
• 引用类型的变量，只可能存储两类值：null 或 地址值（含变量的类型）
• 内存中的一块连续的空间，数组名引用的是这块连续空间的首地址
• 数组的长度一旦确定，就不能修改
• 可以通过数组索引（下标）的方式调用指定位置的元素，速度快
• 从数组底层的运行机制来看，其实没有多维数组。对于二维数组，可以看作是将内层一维数组作为外层一维数组的元素

2. 创建

3. 二维数组

/*
 * 二维数组
 * 1. 静态初始化
 * 2. 动态初始化
 * 3. 索引：如何调用数组的指定位置的元素
 * 4. 如何获取数组的长度
 * 5. 如何遍历数组
 */
@Test
public void test1(){
    //1. 静态初始化
    int[][] arr1 = new int[][]{{1,2,3}, {1,2,3,2,3}, {1}};
    int[] arr2[] = new int[][]{{1,2,3}, {1,2,3,2,3}, {1}};
    int[][] arr3 = {{1,2,3}, {1,2,3,2,3}, {1}};

    //2. 动态初始化
    //内层数组的长度初始为2，通过显式赋值可以改变的；且内层数组由于已开辟内存空间，是具有地址值
    String[][] arr4 = new String[3][2];
    String[][] arr5 = new String[3][];//内层数组由于没有开辟内存空间，地址值null
    System.out.println(arr4.length);//3
    System.out.println(arr4[0].length);//2
    System.out.println(arr4[1].length);//2
    System.out.println(arr4[2].length);//2

    //3. 索引
    //4. 获取数组长度
    arr4[0] = new String[]{"ab", "cd", "adf","adf"};
    System.out.println(arr4[0].length);//4
    System.out.println(arr4[1].length);//2
    System.out.println(arr4[2].length);//2
    System.out.println(arr4[0][3]);//adf

    System.out.println(arr4[0]);//地址值
    System.out.println(arr4[1]);//地址值
    System.out.println(arr4[2]);//地址值

    System.out.println(arr5[0]);//null, 空指针
    System.out.println(arr5[1]);//null, 空指针
    System.out.println(arr5[2]);//null, 空指针
    System.out.println(arr5[2].toString());//java.lang.NullPointerException
    
    //要先开辟空间，才能赋值
	//arr5[0][0] = "a";
	//System.out.println(arr5[0][0]);//NullPointerException
    arr5[0] = new String[3];
    arr5[0][0] = "a";
    System.out.println(arr5[0][0]);//a
}

@Test
public void test2(){
    //5. 遍历二维数组
    int[][] arr = {{1,2,3}, {1,2,3,2,3}, {1}};
    System.out.print("[");
    for(int i=0; i<arr.length; i++){
        System.out.print("[");
        for(int j=0; j<arr[i].length; j++){
            if(j == arr[i].length-1){
                System.out.print(arr[i][j]);
            }else{
                System.out.print(arr[i][j] + " ");
            }
        }
        if(i == arr.length-1){
            System.out.print("]");
        }else{
            System.out.print("], ");
        }
    }
    System.out.print("]");
}//[[1 2 3], [1 2 3 2 3], [1]]
复制代码

4. 数组元素的默认初始化值

5. 数组内存解析

2、Arrays工具类

@Test
public void test1(){
    int[] arr1 = new int[]{1, 2, 3, 4};
    int[] arr2 = new int[]{1, 2, 3, 4};

    boolean isEquals = Arrays.equals(arr1, arr2);
    System.out.println(isEquals);//true
}

@Test
public void test2(){
    int[] arr1 = new int[]{1, 2, 3, 4};
    System.out.println(Arrays.toString(arr1));//[1, 2, 3, 4]
}

@Test
public void test3(){
    int[] arr1 = new int[]{1, 2, 3, 4};
    Arrays.fill(arr1, 0);
    System.out.println(Arrays.toString(arr1));//[0, 0, 0, 0]
}

@Test
public void test4(){
    int[] arr1 = new int[]{23, -2, 32, 4};
    Arrays.sort(arr1);
    System.out.println(Arrays.toString(arr1));
}

@Test
public void test5(){
    int[] arr1 = new int[]{23, -2, 32, 4};
    int index = Arrays.binarySearch(arr1, 32);

    if(index >= 0){
        System.out.println(index);
    }else{
        System.out.println("没找到");
    }
}
复制代码

3、常见算法

/*
 * 求数值型数组中元素的最大值、最小值、平均数、总和等
 * 数组的复制、反转、排序、查找(线性查找、二分法查找)
 */
//1. 求一维数组最大值
//拿数组的第一个数arr[0]与一维数组的其他数比较，大的就赋给x
public int getMax(int[] arr){
    //int maxValue = 0;
    int maxValue = arr[0];
    for(int i=0; i<arr.length; i++){
        if(maxValue < arr[i]){
            maxValue = arr[i];
        }
    }

    return maxValue;
}

//2. 求一维数组最小值
public int getMin(int[] arr){
	//int minValue = 0;
    int minValue = arr[0];
    for(int i=0; i<arr.length; i++){
        if(minValue > arr[i]){
            minValue = arr[i];
        }
    }

    return minValue;
}

//3. 求一维数组总和
public int getSum(int[] arr){
    int sum = 0;
    for(int i=0; i<arr.length; i++){
        sum += arr[i];
    }
    return sum;
}

//4. 求一维数组平均数
public int getAvg(int[] arr){
    return getSum(arr) / arr.length;
}


//1. 数组的复制
public String[] copy(String[] arr){
    String[] arr1 = new String[arr.length];
    for(int i=0; i<arr.length; i++){
        arr1[i] = arr[i];
    }
    return arr1;
}


//2. 数组的反转
public String[] reverse1(String[] arr){
    for(int i=0; i<arr.length/2; i++){
        String temp = arr[i];
        arr[i] = arr[arr.length-1-i];
        arr[arr.length-1-i] = temp;
    }
    return arr;
}

public String[] reverse2(String[] arr){
    for(int i=0, j=arr.length-1; i<arr.length/2; i++, j--){
        String temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    return arr;
}


//线性查找
public int search(String[] arr, String dest){
    int index = -1;
    for(int i=0; i<arr.length; i++){
        if(dest.equals(arr[i])){
            index = i;
            break;
        }
    }
    return index;
}

//二分查找：要求所查找的数组必须有序
public int binarySearch(int[] arr, int dest){
    int index = -1;
    int head = 0;
    int end = arr.length-1;
    while (head<=end){
        int middle = (head + end)/2;
        if(dest == arr[middle]){
            index = middle;
            break;
        }else if(dest > arr[middle]){
            head = middle + 1;
        }else {
            end = middle -1;
        }
    }
    return index;
}
复制代码

杨辉三角

/*
 * 使用二维数组打印一个 10 行杨辉三角
 * 1. 第一行有 1 个元素, 第 n 行有 n 个元素
 * 2. 每一行的第一个元素和最后一个元素都是 1
 * 3. 从第三行开始, 对于非第一个元素和最后一个元素的元素。即：
 *      yanghui[i][j] = yanghui[i-1][j-1] + yanghui[i-1][j];
 *
 *  [0] 1
 *  [1] 1   1
 *  [2] 1   2   1
 *  [3] 1   3   3   1
 *  [4] 1   4   6   4   1
 *  [5] 1   5   10  10  5   1
 *  [6] 1   6   15  20  15  6   1
 *  [7] 1   7   21  35  35  21  7   1
 *  [8] 1   8   28  56  70  56  28  8   1
 *  [9] 1   9   36  84  126 126 84  36  9   1
 *     [0] [1] [2] [3]  [4] [5] [6] [7] [8] [9]
 */

@Test
public void test(){
    //1. 初始化一个二维数组
    int[][] arr = new int[10][];
    
    for(int i = 0; i<arr.length; i++){
        //2. 给每个内层数组开辟空间
        arr[i] = new int[i+1];
        
        //3. 给每行的头尾赋值
        arr[i][0] = 1;
        arr[i][i] = 1;
        
        //4. 给每行的中间元素赋值
        for(int j=1; j<arr[i].length-1; j++){
            arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
        }
    }

    for(int i=0; i<arr.length; i++){
        for(int j=0; j<arr[i].length; j++){
            System.out.print(arr[i][j] + "\t");
        }
        System.out.println();
    }
}
复制代码

冒泡排序

重复地走访过要排序的数列，比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。

public int[] bubbleSort(int[] arr){
    for(int i=0; i<arr.length; i++){
        //每走一趟，会把最大的移动到最后
        //每走一趟，里面都在进行相邻元素的比较
        for(int j=0; j<arr.length-1-i; j++){
            if(arr[j] > arr[j+1]){
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
        	}
        }
    }
    return arr;
}
复制代码

递归方法

/* 
 * 1. 一个方法内部调用它本身 
 * 2. 方法递归包含了一种隐式的循环，它会重复执行某段代码，但这种重复执行无须循环控 
 *    递归一定要向已知方向递归，否则这种递归就变成了无穷递归，类似于死循环。
 */
// 例1：计算1-100之间所有自然数的和
public int getSum(int n){
    if(n == 1){
        return 1;
    }else {
        return n + getSum(n - 1);
    }
}

// 例2：计算1-n之间所有自然数的乘积:n!
public int getSum1(int n){
    if(n == 1){
        return 1;
    }else {
        return n*getSum1(n-1);
    }
}

//例3：已知有一个数列：f(0) = 1,f(1) = 4,f(n+2)=2*f(n+1) + f(n),
//其中n是大于0的整数，求f(10)的值。
public int getSum2(int n){
    if(n == 0){
        return 1;
    }else if(n == 1){
        return 4;
    }
    else{
        return 2*getSum2(n-1) + getSum2(n-2);
    }
}
复制代码