数组

1. 数组的常见操作

1. 数组元素的正反向遍历

2. 获取数组的最大最小值

3. 如何反转数组中的元素

   思想：首尾元素依次互换。

   for (int i = 0; i < arr.length/2; i++){
     int t = arr[i];
     arr[i] = arr[arr.length - 1 - i];
     arr[arr.length - 1 - i] = t;
   }
   

2. 稀疏数组(Sparse Array)

当一个数组大部分元素是0，或者为同一个值的时候可以用稀疏数组进行保存以节约数据。

• 稀疏数组的处理方式是：
  • 记录数组一共有几行几列，多少个不同值。
  • 把具有不同值的元素和行列及值记录在一个小规模的数组中，从而缩小程序的规模。

如：

1 0 0

0 2 0

8 0 0

以上的数组用稀疏数组保存的结果是：

又如：

某原数组用Java表示为

public static int[][] originalList(){
  int[][] ints = new int[11][11];
  ints[0][1] = 1;
  ints[1][2] = 2;
  return ints;
}

/*
0    1    0    0    0    0    0    0    0    0    0    
0    0    2    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
*/

将上面的数组转为稀疏数组

public static int[][] toSparsArray(int[][] ints){
   if (ints.length == 0 || null == ints){
            return null;
   }
  int sum = 0;
  for (int i = 0; i < ints.length; i++) {
    for (int j = 0; j < ints[0].length; j++){
      if(ints[i][j] != 0){
        sum++;
      }
    }
  }
  int[][] array = new int[sum + 1][3];
  array[0][0] = ints.length;
  array[0][1] = ints[0].length;
  array[0][2] = sum;

  int cnt = 0;

  for (int i = 0; i < ints.length; i++) {
    for (int j = 0; j < ints[0].length; j++){
      if(ints[i][j] != 0){
        cnt++;
        array[cnt][0] = i+1;
        array[cnt][1] = j+1;
        array[cnt][2] = ints[i][j];
      }
    }
  }
  return array;
}

/*
11    11    2    
1    2    1    
2    3    2    
*/

将上面的数组恢复成原来的数组

public static int[][] toOriginalArray(int[][] ints){
  if(null == ints || ints.length == 0 || ints[0][0] == 0 || ints[0][1] == 0){
    return null;
  }
  int[][] array = new int[ints[0][0]][ints[0][1]];
  for(int i = 1;i < ints.length; i++){
    array[ints[i][0] - 1][ints[i][1] - 1] = ints[i][2];
  }
  return array;
}

/*
0    1    0    0    0    0    0    0    0    0    0    
0    0    2    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
*/

3. 扩展

3.1. Arrays.sort() 实现二维数组排序

如果需要对二维数组进行排序，需要重写sort()方法中的Comparator比较器。

方式一：普通写法

// 对二维数组按照每行数组的第一个元素进行排序
Arrays.sort(points, new Comparator<int[]>() {
  @Override
  public int compare(int[] o1, int[] o2) {
    // 按照从小到大排序
    return o1[0] - o2[0];
  }
});

方式二：使用Lambda表达式的方式对Comparator比较器进行简写（JDK1.8+）

Arrays.sort(points, o1, o2) -> {
  // 按照从小到大排序
  return o1[0] - o2[0];
});

方式三：使用Comparator.comparingInt()方法

static <T> Comparator<T> comparingInt(ToIntFunction<? super T> keyExtractor)

该方法接收一个函数作为参数，从类型T中提取一个int类型的排序键，并返回一个与该排序键进行比较的Comparator。

Arrays.sort(points, Comparator.comparingInt(o -> o[0]));

方式四：先按某一列排序，如相同再按另一列排序

Arrays.sort(c, new Comparator<int[]>(){ //对二维数组进行排序
  public int compare(int a[],int b[]){
    if(a[1]==b[1]){
      return a[0]-b[0];  // 相等再按第二列排序
    }
    return a[1]-b[1];  //表示先按第一列升序
  }
});  

//和上面的代码功能相同
Arrays.sort(c,(a,b)->a[1]-b[1]);