参考文献

  • 数据结构与算法之美-王争
  • 算法第四版

数组

  • 数组(Array)是一种线性表数据结构.它用一组连续的内存空间,来存储一组具有相同类型的数据.

    • 线性表: 数据排列成像一条线一样的结构.每个线性表上的数据最多只有前和后两个防线.

    • 连续的内存空间和相同类型的数据.

    • 随机访问

      在计算机科学中，随机访问是指能够随机访问给定元素集中的任何项目的功能。

      随机访问也称为直接访问。

    • 数组下标都是从0开始的

    • 数组的元素是不能删除的,只能覆盖

  • 寻址公式

    1
    a[i]_address = base_address + i * data_type_size
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
package com.holelin.array;

/**
 * ClassName: Array
 * 实现动态数组
 *
 * @author HoleLin
 * @version 1.0
 * @date 2019/1/19
 */

public class Array<E> {
	/**
	 * 数组
	 */
	private E[] data;
	/**
	 * 数组中元素是个数
	 */
	private int size;

	/**
	 * 将数组转换为Array
	 *
	 * @param arr 待转换的数组
	 */
	public Array(E[] arr) {
		data = (E[]) new Object[arr.length];
		for (int i = 0; i < arr.length; i++) {
			data[i] = arr[i];
		}
		size = arr.length;
	}

	/**
	 * 根据用户指定容量来创建数组初始容量
	 *
	 * @param capacity 用户指定容量
	 */
	public Array(int capacity) {
		data = (E[]) new Object[capacity];
		size = 0;
	}

	/**
	 * 默认设置数组长度为20
	 */
	public Array() {
		this(20);
	}

	/**
	 * 获得数组中元素的个数
	 *
	 * @return 数组中元素的个数
	 */
	public int getSize() {
		return this.size;
	}

	/**
	 * 获得数组的容量
	 *
	 * @return 数组的容量
	 */
	public int getCapacity() {
		return data.length;
	}

	/**
	 * 判断数组是否为空
	 *
	 * @return 数组是否为空, 非空返回false, 空返回true
	 */
	public boolean isEmpty() {
		return size == 0;
	}

	/**
	 * 在末尾添加元素
	 * 时间复杂度 : O(1)
	 *
	 * @param element 待添加的元素
	 */
	public void addLast(E element) {
		add(size, element);
	}

	/**
	 * 在开头插入元素
	 * 时间复杂度 : O(n)
	 *
	 * @param element 待添加的元素
	 */
	public void addFirst(E element) {
		add(0, element);
	}

	/**
	 * 根据用户指定位置插入元素
	 * 时间复杂度 : O(n)
	 *
	 * @param index   元素插入的位置
	 * @param element 带插入的元素
	 */
	public void add(int index, E element) {
		// 当数组满了则不能添加元素
		if (size == data.length) {
			resize(2 * data.length);
//            throw new IllegalArgumentException("Add failed . Array is full .");
		}
		if (index < 0 || index > size) {
			throw new IllegalArgumentException("Add failed . Require index >=0 and index < size.");
		}
		// 将index位置后的数向后移动一个位置 空出index位置
//        for (int i = size - 1; i >= index; i--) {
//            data[i + 1] = data[i];
//        }
		if (size - index >= 0) {
			System.arraycopy(data, index, data, index + 1, size - index);
		}
		// 将待插入元素插入index位置上
		data[index] = element;
		// 数组元素个数加一
		size++;
	}

	private void resize(int newCapacity) {
		// 创建新的大容量数组
		E[] newData = (E[]) new Object[newCapacity];
		// 将旧数组中元素全部拷贝到新数组中
		System.arraycopy(data, 0, newData, 0, size);
		// 将新数组赋给data
		data = newData;
	}

	/**
	 * 获取index索引位置的元素
	 * 时间复杂度 : O(1)
	 *
	 * @param index 元素的位置
	 * @return index索引位置的元素
	 */
	public E get(int index) {
		if (index < 0 || index >= size) {
			throw new IllegalArgumentException("Get failed. Index is illegal");
		}
		return data[index];
	}

	/**
	 * 获取数组中第一个元素的值
	 *
	 * @return 数组中第一个元素的值
	 */
	public E getFirst() {
		return get(0);
	}

	/**
	 * 获取数组中最后一个元素的值
	 *
	 * @return 数组中最后一个元素的值
	 */
	public E getLast() {
		return get(size - 1);
	}

	/**
	 * 将index位置上的元素修改为element
	 * 时间复杂度 : O(1)
	 *
	 * @param index   要修改元素的位置
	 * @param element 修改后元素的值
	 */
	public void set(int index, E element) {
		if (index < 0 || index >= size) {
			throw new IllegalArgumentException("Get failed. Index is illegal");
		}
		data[index] = element;
	}

	/**
	 * 判断数组中是否包含element元素
	 * 时间复杂度 : O(n)
	 *
	 * @param element 待判断的元素
	 * @return 当数组中包含element返回true
	 */
	public boolean contains(E element) {
		for (int i = 0; i < size; i++) {
			if (data[i] == element) {
				return true;
			}
		}
		return false;
	}

	/**
	 * 查询数组中是否包含element
	 * 时间复杂度 : O(n)
	 *
	 * @param element 待查找的元素
	 * @return 包含返回element所在的索引, 不包含则返回-1
	 */
	public int find(E element) {
		for (int i = 0; i < size; i++) {
			if (data[i] == element) {
				return i;
			}
		}
		return -1;
	}

	/**
	 * 删除index位置上的元素,返回删除的元素
	 * 时间复杂度 : O(n)
	 *
	 * @param index
	 */
	public E remove(int index) {
		if (index < 0 || index >= size) {
			throw new IllegalArgumentException("Remove failed. index >=0 and index < size");
		}
		E element = data[index];
		// 将index位置后的元素向前移动一位

		for (int i = index + 1; i < size; i++) {
			data[i - 1] = data[i];
		}
        /*
         Otherwise, if any of the following is true, an IndexOutOfBoundsException is thrown and the destination is not modified:
            The srcPos argument is negative.    srcPos参数为负数。
            The destPos argument is negative.   destPos参数是负数。
            The length argument is negative.   长度参数是负数。
            srcPos+length is greater than src.length, the length of the source array.   srcPos + length大于src.length，即源数组的长度。
            destPos+length is greater than dest.length, the length of the destination array.   destPos + length大于dest.length，即目标数组的长度。
         */
        /*
        使用System.arraycopy()方法出现异常
        Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException
                at com.holelin.array.Array.remove(Array.java:235)
                at com.holelin.array.Array.removeFirst(Array.java:253)
                at com.holelin.queue.ArrayQueue.dequeue(ArrayQueue.java:31)
                at com.holelin.queue.QueueEfficiencyTest.testQueue(QueueEfficiencyTest.java:34)
                at com.holelin.queue.QueueEfficiencyTest.main(QueueEfficiencyTest.java:20)
         */
//        if (size - index + 1 >= 0) {
//            //public static void (Object src,
//                                  int srcPos,
//                                  Object dest,
//                                  int destPos,
//                                  int length)
//            // src:源数组；	srcPos:源数组要复制的起始位置；
//            // dest:目的数组；	destPos:目的数组放置的起始位置；
//    				// length:复制的长度。
//            // 注意：src and dest都必须是同类型或者可以进行转换类型的数组．
//            System.arraycopy(data, index + 1, data, index, size - index + 1);
//        }
		size--;
		data[size] = null;
		// 当数组中元素个数等于容量的4分之一时,进行缩容
		if (size == data.length / 4 && data.length / 2 != 0) {
			resize(data.length / 2);
		}
		return element;
	}

	/**
	 * 删除数组中第一个元素,并返回元素的值
	 * 时间复杂度 : O(n)
	 *
	 * @return 返回删除元素的值
	 */
	public E removeFirst() {
		return remove(0);
	}

	/**
	 * 删除数组最后一个元素,并返回元素的值
	 * 时间复杂度 : O(1)
	 *
	 * @return 返回删除元素的值
	 */
	public E removeLast() {
		return remove(size - 1);
	}

	/**
	 * 删除指定的元素
	 *
	 * @param element 指定的元素
	 */
	public void removeElement(E element) {
		int index = find(element);
		if (index != -1) {
			remove(index);
		}

	}

	/**
	 * 交换数组中i所在元素和j所在元素的值
	 *
	 * @param i i所在的元素
	 * @param j j所在的元素
	 */
	public void swap(int i, int j) {
		if (i < 0 || i >= size || j < 0 || j >= size) {
			throw new IllegalArgumentException("Index is Illegal.");
		}
		E t = data[i];
		data[i] = data[j];
		data[j] = t;
	}

	@Override
	public String toString() {
		StringBuilder res = new StringBuilder();
		res.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
		res.append('[');
		for (int i = 0; i < size; i++) {
			res.append(data[i]);
			if (i != size - 1) {
				res.append(",");
			}
		}
		res.append(']');
		return res.toString();
	}
}

测试用例

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
package com.holelin.array;

/**
 * ClassName: ArrayTest
 *
 * @author HoleLin
 * @version 1.0
 * @date 2019/1/19
 */

public class ArrayTest {
    public static void main(String[] args) {
        Array<Integer> arr = new Array<>(20);
        for (int i = 0; i < 19; i++) {
            arr.addLast(i);
        }
        System.out.println(arr);
        arr.add(1, 100);
        System.out.println(arr);
        arr.addFirst(-1);
        System.out.println(arr);
        arr.remove(2);
        System.out.println(arr);
        arr.removeElement(5);
        System.out.println(arr);
        arr.removeFirst();
        System.out.println(arr);
        arr.add(1, 100);
        System.out.println(arr);
        arr.add(1, 100);
        System.out.println(arr);
        arr.add(1, 100);
        System.out.println(arr);
        arr.add(1, 100);
        System.out.println(arr);
        arr.remove(2);
        System.out.println(arr);
        arr.remove(2);
        System.out.println(arr);
        arr.remove(2);
        System.out.println(arr);
        arr.remove(2);
        System.out.println(arr);
        arr.remove(2);
        System.out.println(arr);
        arr.remove(2);
        System.out.println(arr);
        arr.remove(2);
        System.out.println(arr);
        arr.remove(2);
        System.out.println(arr);
        arr.remove(2);
        System.out.println(arr);
        arr.remove(2);
        System.out.println(arr);
        arr.remove(2);
        System.out.println(arr);
        arr.remove(2);
        System.out.println(arr);
    }
}

补充知识点

为什么大多数编程语言中,数组要从0开始编号,而不是从1开始?

从数组存储的内存模型上来看,“下标"最确切的定义应该是"偏移(offset)”.如果用a来表示数组的首地址,a[0]就是偏移为0的位置,也就是首地址,a[k]就是表示偏移k个type_size的位置,所以计算a[k]的内存只需要用这个公式:

1
a[k]_address = base_address + k * type_size

但是,如果数组从1开始计数,那么计算数组元素a[k]的内存地址就会变为:

1
a[k]_address = base_address + (k-1) * type_size

对比两个公式,从1开始编号,每次随机访问数组元素都多了一次减法运算,对于CPU来说,就是多了一次减法指令.

典型的数据处理代码

二分查找
1
2
3
4
5
6
7
8
9
10
11
12
public static int indexOf(int[] a, int key) {
    int lo = 0;
    int hi = a.length - 1;
    while (lo <= hi) {
        // Key is in a[lo..hi] or not present.
        int mid = lo + (hi - lo) / 2;
        if      (key < a[mid]) hi = mid - 1;
        else if (key > a[mid]) lo = mid + 1;
        else return mid;
    }
    return -1;
}
找出数组中最大的元素
1
2
3
4
5
6
double max = a[0];
for(int i = 1; i < a.length; i++){
  if(a[i] > max){
    max = a[i];
  }
}
计算数组元素的平均值
1
2
3
4
5
6
int N = a.length;
double sum = 0.0;
for(int i = 0; i < N; i++){
   sum += a[i];
}
double average = sum / N;
复制数组
1
2
3
4
5
int N = a.length;
double[] b = new  double[N];
for(int i = 0; i < N; i++){
  b[i] = a[i]
}
颠倒数组元素的顺序
1
2
3
4
5
6
int N = a.length;
for(int i = 0; i < N/2; i++){
  double temp = a[i];
  a[i] = a[N-1-i];
  a[N-1-i] = temp;
}
矩阵相乘(方阵)a[][] * b[][] = c[][]
  • 设A为m×pm \times p的矩阵，B为 $p \times n 的矩阵，那么称的矩阵，那么称m \times n的矩阵C为矩阵A与B的乘积，记作的矩阵C为矩阵A与B的乘积，记作C=AB$ ，其中矩阵C中的第ii行第jj列元素可以表示为:

    (AB)ij=∑k=1paikbkj=ai1b1j+ai2b2j+...+aipbpj(AB)_{ij}=\sum_{k=1}^{p}a_{ik}b_{kj}=a_{i1}b_{1j}+ a_{i2}b_{2j}+...+a_{ip}b_{pj}

A=[a1,1a1,2b1,3a2,1c2,2d2,3]A=\begin{bmatrix} a_{1,1} &a_{1,2} &b_{1,3} \\ a_{2,1} &c_{2,2} &d_{2,3} \end{bmatrix}

B=[b1,1b1,2b2,1b2,2b3,1b3,2]B=\begin{bmatrix} b_{1,1}&b_{1,2} \\ b_{2,1}&b_{2,2} \\ b_{3,1}&b_{3,2} \end{bmatrix} 

1
2
3
4
5
6
7
8
9
10
int N = a.length;
doublep[][] c = new double[N][N];
for(int i = 0; i < N; i++){
  for(int j = 0; j < N; j++){
    // 计算行i和列j的点乘
    for(int p = 0; p < N; p++){
      c[i][j] += a[i][p] * b[p][j];
    }
  }
}