数组相关算法

一、数组中涉及到的常见算法

  • 数组元素的赋值（杨辉三角、回形数等）

    • 获取一个两位数的随机数
      1. (int)(Math.random()*(99 - 10 + 1) + 10)

  • 求数值型数组中元素的最大值、最小值、平均数、总和等

    • 求最大值，最小值的注意点：数组第一个元素复制给maxValue，以防数组中有0的时候的情况。

  • 数组的复制、反转、查找（线性查找、二分查找）

    • 注意数组反转的循环条件i < arr.length/2，有两种方法
      1. //数组的反转方式一
      2. for(int i = 0; i < a.length/2; i++) {    //极其容易弄错成i < a.length;
      3. int temp = a[i];
      4. a[i] = a[a.length-i-1];
      5. a[a.length-i-1] = temp;
      6. }
      7. //数组反转方式二
      8. for(int i = 0, int j = a.length-1; i < j; i++, j--){
      9. int temp = a[i];
      10. a[i] = a[j];
      11. a[j] = temp;
      12. }
  • 二分查找的前提是所查找的数组必须有序（递归实现和非递归实现），java.util.Arrays源码用的是非递归实现
    1. //二分查找方式一：用非递归方式实现二分查找
    2.    public static int binarySearch1(int[] a, int dest) {
    3.        int low = 0;
    4.        int high = a.length-1;
    5.        while(low <= high) {
    6.            int mid = (low + high)/2;
    7.            if(a[mid] == dest) {
    8.                return mid;//返回dest在数字a中的数组下标
    9.            }else if(dest > a[mid]) {
    10.                low = mid + 1;
    11.            }else if(dest < a[mid]) {
    12.                high = mid - 1;
    13.            }
    14.        }
    15.        return -1;//没有找到返回-1
    16.    }
    17. //二分查找方式二：用递归方式实现二分查找
    18.    public static int binarySearch2(int[] a, int low, int high, int dest) {
    19.        //if(dest < a[low] || dest > a[high]) {
    20.        //    return -1;
    21.        //}
    22.        if(low > high){
    23.            return -1;
    24.        }
    25.        int mid = (low+high)/2;
    26.        if(dest > a[mid]) {
    27.            return binarySearch2(a, mid + 1, high, dest);
    28.        }else if(dest < a[mid]) {
    29.            return binarySearch2(a, low, mid - 1, dest);
    30.        }else {
    31.            return mid;
    32.        }
    33.    }

  • 数组元素的排序算法
    day07_java数组相关算法学习笔记 - 图1
    day07_java数组相关算法学习笔记 - 图2

    • 衡量排序算法的优劣：时间复杂度、空间复杂度、稳定性。

    • 需要掌握冒泡排序和快速排序的手写

  • 笔试题
    day07_java数组相关算法学习笔记 - 图3

二、Arrays工具类的使用

day07_java数组相关算法学习笔记 - 图4

Arrays.toString(int[] a)底层用到是stringBuilder

void fill(int[] a,int val)把val这个值填充到数组中，数组中所有的元素都换成val

void sort(int[] a)底层用到是快速排序

int binarySearch(int[],int key)前提是数组有序，源码用的是非递归的二分查找

三、数组使用中常见的异常

  • 数组角标越界的异常：ArrayIndexOuttOfBoundsException
  • 空指针异常：NullPointerException