Java-3-Array
Introduction
这一章介绍Java 里面的Array数组的操作和原理。 这里会先简单介绍一下数组的概念和以及数组的基本操作(创建，遍历修改，排序，更加高维度的数组的操作等)
1. 数组基本概念 Concept
1.1 什么是数组
首先什么是数组? 数组是一种数据结构不管在哪种编程语言都会用到， 它就好比是我们的有很多抽屉的柜子，每个抽屉都有自己的ID(比如位置)来识别每个抽屉的位置，而根据ID我们打开相应的抽屉时就能够有对应的空间让我们放东西。
和这个柜子的特点一样， 数组有以下特点:
- 固定长度(柜子的大小和抽屉的个数是固定的)
- 类型相同(这个柜子只能放一类的物品)
- 可以通ID寻址(比如按照柜子的抽屉的高度顺序来标号)
1.2 数组的底层内存构成 (Memory of Array)
在Java里面假设我有一个array名字叫做a, 我们可以把它看成是一个柜子的名字a, 然后我这个柜子里面存放的是叫做 int整型的数据(物品)， 那么我这个这个柜子有5个抽屉，那么在创建数组时就是写成int a[] = new int[5]。 而这个时候这个array的名字地址a就放到stack栈里面，相对于把这个柜子的名字放到一个列表，方便知道柜子在什么地方。而柜子的内容放到一个叫heap堆的空间里面。当我们要用时就先找a的地址，然后再再找第i个抽屉，把数据拿出来。即 读取a[i]的数据。
上面提及的存放array的名字和数据的内存有以下:
Stack 栈内存：栈内存存储的都是局部变量，变量一旦出了自己的作用域，那么就会马上从内存的消失，释放内存空间。
Heap 堆内存：堆内存存储的都是对象内存，对象一旦被使用完，并不会马上从内存中消失，而是等待垃圾回收器不定时的把垃圾对象回收，这时候该对象才会消失，释放内存。
凡是以new关键字创建的对象，JVM都会在堆内存中开辟一个新的空间，创建一个新的对象。 对象如果没有变量引用了，那么该对象就是一个垃圾对象了。
2. 数组基本操作Array Operations
2.1 数组创建Creation
- 数组申明 declaration
当我们想要告诉程序，我们要定义一个数组，但还没有初始化赋予空间时，我们可以简单通过下面语句declare。 第一种是Java的常见写法，第二种是C++的写法。但是这样做，数组还没有开储存空间，所以不能直接用，这样就涉及到数组的初始化。1
2
3
4int [] arr;
//or
int arr[];
- 数组初始化 Initialization
在Java里面初始化数组一般要new关键词， 除非是定义数组同时直接赋值。
在数组的初始化我们可以用下面方法定义数组并赋值：
- 先定义后赋值 或者
1
2
3
4
5int [] a;
a = new int[5];
a[0] = 1;
a[1] = 2;
...1
2int [] a;
a = new int[5]{1,2,3,4,5}; - 定义的同时赋值
1
int [] a = {1,2,3,4,5}
2.2 数组遍历Iteration
方法1: 用index遍历数组
在Java的数组里， 数组的index都是从0开始的，所以如果有n个元素在数组，那么就最大的index = n-1. 比如以下代码里面对a数组打印是从0打印到4， a数组的大小为5.1
2
3
4
5
6
7
8
9public class Demo{
public static void main(){
int [] a = {1,2,3,4,5};
for(int i=0; i< a.length; i++){
System.out.println(a[i]);
}
}
}方法2: 用for each 遍历数组
另外一种数组的遍历是用for each来遍历有点类似python里面的for x in ls:的用法，以及C++里面的for(auto x : ls)的用法。 for each的方法要比index遍历的方法简洁，但是不能拿到index，只能直接拿数据item。1
2
3
4
5
6
7
8public class Main {
public static void main(String[] args) {
int[] ns = { 1, 4, 9, 16, 25 };
for (int n : ns) {
System.out.println(n);
}
}
}
2.3 数组的常用的API
Arrays.sort()
排序是数据结构算法的很基础的一个操作，因此Array的类也有对应的API. 这里我们先调用这个API，再尝试自己写一个。
这里我们先通过java.util.Arrays调用Array 类然后再调用这个类里面的Array.sort()的方法。 Note: Array.sort()的方法的输入可以是不同的类，如int, float, double, String 等，如果是String会按照第一个字母的ASCII码进行排序1
2
3
4
5
6
7
8
9import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] ns = { 12,0,-4,-9, 20, 30, -100};
Arrays.sort(ns);
System.out.println(Arrays.toString(ns));
}
}这里实现一个insertion sort
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31// 降序排序
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] ns = { 28, 12, 89, 73, 65, 18, 96, 50, 8, 36 };
// 排序前:
System.out.println(Arrays.toString(ns));
// TODO: insertion sort
int tmp;
for(int i=0; i< ns.length-1;i++){
tmp = ns[i];
//find max
for(int j= i+1; j< ns.length;j++ ){
if(ns[j]> tmp){
tmp = ns[j];
ns[j] = ns[i];
ns[i] = tmp;
}
}
}
// 排序后:
System.out.println(Arrays.toString(ns));
if (Arrays.toString(ns).equals("[96, 89, 73, 65, 50, 36, 28, 18, 12, 8]")) {
System.out.println("测试成功");
} else {
System.out.println("测试失败");
}
}
}Arrays.toString()
Array的toString函数可以把一个array(包括中括号[]) 转成一个String， 比如把[96, 89, 73, 65, 50, 36, 28, 18, 12, 8] 转成 “[96, 89, 73, 65, 50, 36, 28, 18, 12, 8]”。1
2
3
4
5
6
7
8
9
10
11
12
13
14public class Main {
public static void main(String[] args) {
int[] ns = { 28, 12, 89, 73, 65, 18, 96, 50, 8, 36 };
// 排序前:
System.out.println(Arrays.toString(ns));
System.out.println(Arrays.toString(ns));
if (Arrays.toString(ns).equals("[28, 12, 89, 73, 65, 18, 96, 50, 8, 36]")) {
System.out.println("测试成功");
} else {
System.out.println("测试失败");
}
}
}Arrays.fill()
数组中的元素定义完成后，可通过Arrays类的静态方法fill()方法来对数组中的元素进行分配，起到填充和替换的效果。fill()方法可将指定的int值分配给int型数组的每个元素。用法∶Arrays.fill(int[] a ,int value)
2.4 更高维度的数组Higher dimensional array
2.4.1 2D array
2D array的创建和1D的差不多,一样用new关键词进行创建。不过2D array里面每一行的长度可以不一样。array[row][col] 2D array的第一个index代表row的index，第二个index是column的index.
以上面图为例， array是一个存放了每个row的起始的地址的列表，而 array[i] 地址指向了第i个row的数组。而2D array的每个element都是放到Heap里面的
1 | int[][] a = {{1}, {1,2}, {1,2,3}}; |
1 | public class Main { |
在上面这个数组里面，它的结构是
1 | ns[0][1].........ns[0][3] |
3. Coding Practice
这里我自己写一个2D binary Search 的leetcode的题目来练习一下2D array
1 | import java.util.Arrays; |
Compile Commands:
1 | $ javac Task3.java |
Output:
1 | Array: |
4. Comparison between C++ Array and Java Array
| Properties | C++ Array | Java Array |
|---|---|---|
| Type | NOT Object/Class | Java Array is a Class |
| Declaration | int arr[size]= {…} |
int[] arr = new int[size] //usually use “new” |
| Initialization | int arr[size] | int[] arr |
| check size of array | sizeof() | array.length |
5. Reference
[2] Java Tutorial: https://www.liaoxuefeng.com/wiki/1252599548343744/1259544232593792
[3] Datawhale: https://github.com/datawhalechina/team-learning-program/blob/master/Java/4.%E6%95%B0%E7%BB%84.md