day08_数组进阶

今日内容

零、 复习昨日
一、作业
二、引用类型[重要]
三、数组排序[面试|笔试]
四、Arrays
五、数组拷贝
六、数组扩容

零、 复习昨日

方法的参数列表是什么意思?怎么定义的?

• 参数就是方法执行所需要的数据,形参
• 定义方式就是定义变量,int a,多个之间逗号隔开

方法如何调用?

• 方法名(参数);

方法的返回值什么意思?返回给谁?

• 方法执行后返回的数据
• 返回给调用者

数组创建后能否改变长度

• 不能改变,容量固定

数组创建后能否存储不同类型的数据

• 不能,只能存储同类型

遍历是什么意思,尝试手写遍历代码

• 遍历就是找到数组的每一个元素(扫描到每一个)

数组的长度属性

• length

一、作业

package com.qf.homework;

/**
 * --- 天道酬勤 ---
 *
 * @author QiuShiju
 * @date 2024/1/24
 * @desc
 */
public class Homework {

    public static void main(String[] args) {
        int i = findIndexByElement(15);
        if (i != -1) {
            System.out.println("数组中包含该元素");
        } else {
            System.out.println("数组中不包含该元素");
        }
    }


    // 给定一个数组，传入一个数字，如果在数组中存在这个数字，
    // 返回这个数字在数组中的下标，否则返回-1    (根据数据找下标)
    // 这个题,主要目的不是找下标,可以通过下标判断数组中是否包含这个元素
    public static int findIndexByElement(int e) {
        int[] arr = {1, 2, 3, 4, 5};
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == e) {
                return i;
            }
        }
        return -1;// -1意味着没找到
    }

    // 根据下标找元素
    public static int findElementByIndex(int i){
        int[] arr = {1, 2, 3, 4, 5};
        if (i >= 0 && i < arr.length) {
            return arr[i];
        }
        return -10000;// 标志,意味着失败
    }

}

二、引用类型[重要]

java的数据类型

• 基本数据类型
  • 四类八种
  • 基本的意思是,变量代表的就是数据本身
• 引用数据类型
  • 数组,类,接口
  • 引用数据类型,变量代表的不是数据,而是引用的其他的数据

2.1 基本数据类型

基本类型的特点

• 随着方法进栈
• 调用方法传递参数,是将数据本身传递给方法
• 方法执行完,弹栈消失,即方法内的变量也会消失

总结: 基本类型数据在传递过程中,传递的是值

public static void main(String[] args) {
        int v = 10;
        System.out.println("1 v = " + v );// v=10
        changeBaseValue(v);
        System.out.println("4 v = " + v ); // v=10

    }
    // 演示基本数据类型
    public static void changeBaseValue(int v){
        System.out.println("2 v = " + v );// v=10
        v += 10;
        System.out.println("3 v = " + v );// v=20
    }

2.2 引用类型

引用类型,数组类接口这些,都是需要new的

• 凡是new都会在堆中出现
• 数组new也是堆中,方法中的 arr是地址值,是引用堆中的数组

总结: 引用类型传递是对象的地址值,而不是对象本身!

	public static void main(String[] args) {
        int[] arr = {1,2,3,4};
        System.out.print("第1次遍历:" );
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println( );

        changeRefValue(arr);// 调用方法,传递参数,此处传递是数组的地址

        System.out.print("第4次遍历:" );
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println( );
    }

    // 演示引用类型
    public static void changeRefValue(int[] arr){
        System.out.print("第2次遍历:" );
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
            arr[i] = arr[i] * 10;// 将数组元素放大10倍
        }
        System.out.println( );

        System.out.print("第3次遍历:" );
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println( );
    }

2.3 总结

基本类型,值传递

引用类型,地址传递

三、数组排序[面试|笔试]

数组排序算法

• 冒泡排序,选择排序,插入排序

• 快速排序,堆排序,希尔排序,归并排序

• 桶排序,基数排序,计数排序

3.1 冒泡排序

package com.qf.array;

/**
 * --- 天道酬勤 ---
 *
 * @author QiuShiju
 * @date 2024/1/24
 * @desc 冒泡排序
 */
public class Demo2 {
    public static void main(String[] args) {
        int[] arr = {5,4,3,2,1};
        System.out.println("排序前:" );
        printArr(arr);
        // 实现排序,将数组变成{1,2,3,4,5}
        /**
         * 思路: 依次相邻两个判断大小,将大的放后面,小的放前面
         */
        // 外层循环控制趟数 -1是为了第五趟不用比较
        for (int i = 0; i < arr.length - 1; i++) {
            // -1防止下标越界 -i是为了每一趟内比上一趟少比较1次
            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;
                }
            }
        }

        System.out.println("排序后:" );
        printArr(arr);
    }

    // 设计方法,方便遍历数组
    public static void printArr(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println( );
    }
}

思路: 相邻两个依次比较,交互位置,大的放后面小的放后面,然后从头多来几趟,知道找到全部最大的

3.2 选择排序

选择排序思路:

• 第一趟: 假定第一个数最小,遍历后面每一个元素,如果发现有更小,记录位置,直到遍历结束;这个最小的这个位置语与第1个交换位置
• 第二趟: 假定第二个数最小,遍历后面每一个元素,如果发现有更小,记录位置,直到遍历结束;这个最小的这个位置语与第2个交换位置

package com.qf.array;

/**
 * --- 天道酬勤 ---
 *
 * @author QiuShiju
 * @date 2024/1/24
 * @desc 选择排序
 */
public class Demo3 {

    public static void main(String[] args) {
        int[] arr = {5,4,7,6,3,2,1};
        printArr(arr);
        sort(arr);
        printArr(arr);
    }
    public static void sort(int[] arr){
        // 开始排序
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]){
                    minIndex = j;
                }
            }
            // 交换位置
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

    // 设计方法,方便遍历数组
    public static void printArr(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println( );
    }
}

四、Arrays

Arrays , java提供的一个工具类,专用于操作数组的.

主要学习两个方法

• toString(数组), 作用 是将数组以字符串的形式返回
• sort(数组) , 排序(只能从小到大)

public class Demo4 {
    public static void main(String[] args) {
        int[] arr = {5,3,2,1,4};
        /**
         * 使用方式:
         * 类名.方法名(参数)
         */
        // String string = Arrays.toString(arr);
        // System.out.println(string );

        System.out.println(Arrays.toString(arr) );
        Arrays.sort(arr); // 排序
        System.out.println(Arrays.toString(arr) );
        /**
         * 方法不在当前类,需要通过类名来调用
         * 用类名直接调用方法的前提是,方法有static
         */
        Demo4.myMethod();
        Demo3.printArr(arr);
    }

    public static void myMethod(){
    }
}

五、数组拷贝[熟悉]

将一个数组中的元素复制到另外一个数组中.

5.1 自己手动实现

public class Demo5 {
    public static void main(String[] args) {
        int[] arr1 = {1, 2, 3, 4, 5};
        int[] arr2 = new int[arr1.length];

        System.out.println("arr2 : " + Arrays.toString(arr2) );
        copyByMySelf(arr1, arr2);
        System.out.println("arr2 : " + Arrays.toString(arr2));
    }

    // 数组拷贝,自己实现
    public static void copyByMySelf(int[] arr1, int[] arr2) {
        // 将arr1中的元素,复制到arr2中,将arr2返回
        for (int i = 0; i < arr1.length; i++) {
            arr2[i] = arr1[i];
        }
    }
}

5.2 Arrays实现

Arrays.copyOf()实现数组拷贝

    // 通过Arrays实现数组拷贝
    public static int[] copyByArrays(int[] arr){
        int[] newArr = Arrays.copyOf(arr, 2*arr.length);
        // 会帮我们创建数组,并拷贝元素
        return newArr;
    }

5.3 System实现

    public static int[] copyBySystem(int[] arr){
        /**
         * System 是jdk提供的类
         * arraycopy()是其中的方法,完成数组拷贝
         * 其中有5个参数
         * 参数1: src(source) 源数组
         * 参数2: srcPos(position) 拷贝的起始位置
         * 参数3: dest(destination) 目的数组
         * 参数4: destPos   目的地数组起始位置
         * 参数5: length  拷贝的个数
         */
        int[] arr2 = new int[arr.length * 2];
        System.arraycopy(arr,1,arr2,1,3);
        return arr2;
    }

六、数组扩容[了解]

数组创建完,长度不能改变!!!

这里"扩容",是指向数组存储元素,发现长度不够,此时创建一个新数组,将老数组元素拷贝的新的长的数组,再加入新元素

package com.qf.array;

import java.util.Arrays;

/**
 * --- 天道酬勤 ---
 *
 * @author QiuShiju
 * @date 2024/1/24
 * @desc 数组扩容
 */
public class Demo6 {

    // 前提: 不考虑存储0这个数据,因为0是整型的默认值
    // 没有办法区分这个0是默认值,还是存储的元素
    // 所以: 指定0以为者此处没有元素,可存储

    public static void main(String[] args) {
        int[] arr = {1,2,3};
        arr = add(arr, 4);
        System.out.println(Arrays.toString(arr) );

        arr = add(arr, 5);
        System.out.println(Arrays.toString(arr) );

        arr = add(arr, 6);
        System.out.println(Arrays.toString(arr) );

        arr = add(arr, 7);
        System.out.println(Arrays.toString(arr) );
    }

    /**
     * 题目需求: 向指定数组中添加元素,如果长度不够,扩容2倍再添加
     */
    public static int[] add(int[] arr,int e){
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 0){
                arr[i] = e;
                return arr;
            }
        }
        int index = arr.length;
        // 走到这里,说明数组已满,开始扩容2倍
        arr = Arrays.copyOf(arr, arr.length * 2);
        arr[index] = e;
        return  arr;
    }
}

七、二维数组(略)

八、练习

写一个方法 用于合并两个int类型的数组 合并法则如下
{1,2,5,3,8,9} {1,3,0}---->{0,1,2,3,5,8,9} (合并,去重,并排序)

package com.qf.array;

import java.util.Arrays;

/**
 * --- 天道酬勤 ---
 *
 * @author QiuShiju
 * @date 2024/1/24
 * @desc数组练习题
 */
public class Demo7 {
    public static void main(String[] args) {
        int[] arr1 = {1, 2, 5, 3, 8, 9};
        int[] arr2 = {1, 3, 0,2};

        int[] arr = concatArr(arr1, arr2);
        System.out.println(Arrays.toString(arr));
    }

    public static int[] concatArr(int[] arr1, int[] arr2) {
        // 合并
        int[] arr3 = new int[arr1.length + arr2.length];
        System.arraycopy(arr1,0,arr3,0,arr1.length);
        System.arraycopy(arr2,0,arr3,arr1.length,arr2.length);

        // 去重
        /**
         * 思路: 创建一个新数组,其中存储的是不重复的元素
         * 1) 新数组长度与arr3一样长
         * 2) 拿着老数组中的元素与新数组的中元素比较,没有出现就存储
         */
        int[] arr4 = new int[arr3.length];// arr4是准备存储不重复元素的数组
        int index = 0; // 用来记录存储到arr4的下标的
        for (int i = 0; i < arr3.length; i++) {// 遍历取出老数组的每一个
            int e = arr3[i];
            boolean isDuplicate = false;// 标记,用来判断是否有重复元素
            for (int j = 0; j < arr4.length; j++) {// 遍历取出新数组的每一个
                if (e == arr4[j]){// 如果发现2个数组有相同元素
                    isDuplicate = true;// 标记就记录有相同
                }
            }
            // 在arr4中循环比较完一遍,发现没有重复元素
            // 将元素存储到arr4
            if (!isDuplicate){
                arr4[index] = e;
                index++;
            }
        }

        // arr4中有空余位置,再创新造一个小点数组
        int[] arr5 = new int[index];
        System.arraycopy(arr4,0,arr5,0,index);
        // 排序
        Arrays.sort(arr5);
        return arr5;
    }
}

总结

重点

1. 理解引用类型,理解内存图
2. 排序算法要会手写
3. Arrays工具类会用

附录

element 元素

index 下标

find 查找

change 改变

base 基础

value值

reference 引用,一般ref

concat 合并