数组基础

Java基础

浏览数:131

2019-10-3

AD:资源代下载服务

前提

算法中大多数用到数组,理解数组是学习算法的前提。下面用小白的角度重新记录一下数组相关的知识,包括声明、使用等等,不涉及JVM层面。主要介绍基本类型整型的数组,其他类型类同。参考资料:

数组简介

数组表示同一种类型数据的集合。其实数组就是一个容器。运算的时候有很多数据参与运算,那么首先需要做的是什么。不是如何运算而是如何保存这些数据以便于后期的运算,那么数组就是一种用于存储数据的方式,能存数据的地方我们称之为容器,容器里装的东西就是数组的元素, 数组可以装任意类型的数据,虽然可以装任意类型的数据,但是定义好的数组只能装一种元素,也就是数组一旦定义,那么里边存储的数据类型也就确定了。

数组声明

一维数组声明

声明格式一:元素类型[] 数组名 = new 元素类型[元素个数或数组长度];

例如:int[] arr = new int[5];

声明格式二:元素类型[] 数组名 = new 元素类型[]{元素1,元素2,…元素n};

例如:int[] arr = new int[]{3,5,1,7};

声明格式三:元素类型[] 数组名 = {元素1,元素2,…元素n};

例如:int[] arr = {3,5,1,7};

多维数组声明

例如二维数组的声明跟一维数组大致相同:

元素类型[][] 数组名 = new 元素类型[第一维数组的长度][第二维数组的长度];

小结

其实可以这样类比:一维数组类比为一维坐标轴,二维数组类比为二维坐标轴,三维数组类比为三维坐标轴…。

注意事项和常见异常

数组下标从0开始

数组下标从0开始,也就是第一个元素的索引值为0,而索引值为1是第二个元素的下标。

int[] arr = new int[]{3,5,1,7};
-->arr[0]值为3
-->arr[1]值为5

空指针异常

一般出现NPE(NullPointerException)是因为访问了null对象的属性或者是调用了null对象的方法。例如:

int[] x = { 1, 2, 3 };
x = null;
System.out.println(x[1]);
// java.lang.NullPointerException

索引值越界异常

一般出现ArrayIndexOutOfBoundsException(俗称数组越界异常)是因为访问了不存在的数组索引值。例如:

int[] x = { 1, 2, 3 };
System.out.println(x[3]);
//java.lang.ArrayIndexOutOfBoundsException

无法实例化泛型数组

这个和Java的泛型机制相关,这里不深入展开。也就是说数组在实例化的时候类型必须是具体的,不能带有泛型参数。但是注意,泛型数组可以作为变量。例如:

T[] t = new T[5]; //编译无法通过

//泛型数组可以作为变量
public <T> void sort(T[] ts){
    //todo
}

数组常用的操作

元素遍历

直接用for循环或者foreach即可。

    private static void traverse(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }

元素插入

新元素通过下标插入,如果确定不会越界的话,需要把数组扩容,容量加1,下标所有位置后面的所有元素都要后移一个位置。

    private static int[] insert(int index, int value, int[] array) {
        //先判断是否越界
        if (index < 0 || index > array.length) {
            throw new IllegalArgumentException("index");
        }
        int[] newArray = new int[array.length + 1];
        //index下标前面的元素复制
        for (int i = 0; i < index; i++) {
            newArray[i] = array[i];
        }
        //index下标元素赋值
        newArray[index] = value;
        //index下标后面的元素后移动一个位置
        for (int k = index + 1; k < newArray.length; k++) {
            newArray[k] = array[k - 1];
        }
        return newArray;
    }

当然,可以通过数组的拷贝API简化如下:

    private static int[] insert(int[] array, int value, int index) {
        int length = array.length;
        int[] newArray = new int[length + 1];
        System.arraycopy(array, 0, newArray, 0, index);
        newArray[index] = value;
        System.arraycopy(array, index, newArray, index + 1, length - index);
        return newArray;
    }

元素替换

元素替换比元素插入简单,如果确定不会越界的话直接替换掉对应下标的元素值即可。

    private static int[] replace(int index, int value, int[] array){
        //先判断是否越界
        if (index < 0 || index >= array.length) {
            throw new IllegalArgumentException("index");
        }
        array[index] = value;
        return array;
    }

元素移除

元素移除可以看作是元素插入的逆向操作,如果确定不会越界的话,需要把数组减容,容量减1,下标所有位置后面的所有元素都要前移一个位置。

    private static int[] remove(int index, int[] array) {
        if (index < 0 || index >= array.length) {
            throw new IllegalArgumentException("index");
        }
        int[] newArray = new int[array.length - 1];
        for (int i = 0; i < index; i++) {
            newArray[i] = array[i];
        }
        for (int k = index + 1; k <= newArray.length; k++) {
            newArray[k - 1] = array[k];
        }
        return newArray;
    }

或者使用数组拷贝的API:

    private static int[] remove(int index, int[] array) {
        if (index < 0 || index >= array.length) {
            throw new IllegalArgumentException("index");
        }
        int length = array.length;
        int[] newArray = new int[length - 1];
        System.arraycopy(array, 0, newArray, 0, index - 1);
        System.arraycopy(array, index, newArray, index - 1, length - index);
        return newArray;
    }

元素查找

通过下标查找看起来有点多余:

    private static int search(int index, int[] array){
        if (index < 0 || index >= array.length) {
            throw new IllegalArgumentException("index");
        }
        return array[index];
    }

有序数组操作

有序数组的元素插入、替换、移除是不需要依赖传入下标值,因为可以通过元素的比较得到需要操作的元素下标,有序数组的元素的查找可以使用二分查找以提高效率。

   private static void print(int[] array) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < array.length; i++) {
            builder.append(array[i]).append(",");
        }
        System.out.println(builder.substring(0, builder.lastIndexOf(",")));
    }

    private static int[] insert(int target, int[] array) {
        int length = array.length;
        int index = length;
        //先判断新元素的下标
        for (int i = 0; i < length; i++) {
            if (target < array[i]) {
                index = i;
                break;
            }
        }
        int[] newArray = new int[length + 1];
        //下标前面的元素复制
        for (int j = 0; j < index; j++) {
            newArray[j] = array[j];
        }
        newArray[index] = target;
        //下标后面的元素后移
        for (int k = index + 1; k < newArray.length; k++) {
            newArray[k] = array[k - 1];
        }
        return newArray;
    }

    private static int[] replace(int target, int[] array) {
        int length = array.length;
        int index = length;
        //先判断新元素的下标
        for (int i = 0; i < length; i++) {
            if (target < array[i]) {
                index = i;
                break;
            }
        }
        //修正差距,选择差距最小的值进行替换
        if (array[index] - target > target - array[index - 1]) {
            index = index - 1;
        }
        array[index] = target;
        return array;
    }

    private static int[] remove(int target, int[] array) {
        int length = array.length;
        int index = length;
        //先判断新元素的下标
        for (int i = 0; i < length; i++) {
            if (target < array[i]) {
                index = i;
                break;
            }
        }
        //修正差距,选择差距最小的值进行替换
        if (array[index] - target > target - array[index - 1]) {
            index = index - 1;
        }
        int[] newArray = new int[array.length - 1];
        for (int i = 0; i < index; i++) {
            newArray[i] = array[i];
        }
        for (int k = index + 1; k <= newArray.length; k++) {
            newArray[k - 1] = array[k];
        }
        return newArray;
    }

    private static int binarySearch(int target, int[] array) {
        int lower = 0;
        int upper = array.length - 1;
        while (lower <= upper) {
            int mid = (lower + upper) / 2;
            int midValue = array[mid];
            if (midValue < target) {
                lower = mid + 1;
            } else if (midValue > target) {
                upper = mid - 1;
            } else {
                return mid;
            }
        }
        return -(lower + 1);
    }

对于二分查找,有现成的工具方法:java.util.Arrays#binarySearch,上面的二分搜索方法也是直接参考里面的实现。Arrays.binarySearch方法使用前,需要对数组排序,才能定位值插入位置,因为binarySearch采用二分搜索法。可以借鉴这个思路,处理非有序数组的时候,先使用java.util.Arrays#sort对数组进行排序,再使用java.util.Arrays#binarySearch。不过如果排序的耗时过多会得不偿失,这个可以自己衡量一下。在空闲的时候看了下java.util.Arrays里面的排序算法,发现了java.util.DualPivotQuicksortjava.util.TimSort才深知大神的厉害和自己的渺小。

小结

其实一直纠结算法学习怎么入手,到底看Java的实现还是C的实现。后来发现纠结是浪费时间,索性先看Java再重新学习一下C。推荐的资料如下(现在还没有看,打算一本一本地啃):

  • 数据结构于算法分析-Java语言描述(或者C语言描述)
  • Jdk中的两个类java.util.DualPivotQuicksortjava.util.TimSort
  • The Algorithm Design Manual
  • Algorithms 4th

主要推送的资料来自一个大神的书单:我的算法学习之路

能不能坚持下去谁也不知道,共勉。

(本文完)

作者:throwable