-
Notifications
You must be signed in to change notification settings - Fork 4
/
Array.ts
246 lines (222 loc) · 5.54 KB
/
Array.ts
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
export default class MyArray<E> {
public data: E[];
public size: number = 0;
/**
* 构造函数,传入数组的容量capacity
* @param {number} capacity 数组容量,默认10
*/
constructor(capacity = 10) {
this.data = new Array(capacity);
}
/**
* 获取数组容量(数组能总共能包含多少元素)
* Time Complexity O(1)
* @return {number}
*/
getCapacity(): number {
return this.data.length;
}
/**
* 获取数组中当前存储元素的个数
* Time Complexity O(1)
* @return {number}
*/
getSize(): number {
return this.size;
}
/**
* 判断数组是否为空,即元素的个数是否为0
* Time Complexity O(1)
* @return {boolean}
*/
isEmpty(): boolean {
return this.size === 0;
}
/**
* 在数组中index位置添加一个元素
* 考虑到这里不是每次操作都会触发扩容,这里均摊到每次操作上的时间复杂度为O(1)
* @param {number} index 要插入的位置
* @param {E} e 要插入的元素
* @return {void}
*/
add(index: number, e: E): void {
if (index < 0 || index > this.size) {
throw new Error('Add failed. Required index >= 0 and index <= size');
}
// 将数组的容量扩大为之前的二倍
if (this.size === this.data.length) {
this.resize(this.data.length * 2);
}
for (let i = this.size - 1; i >= index; i--) {
this.data[i + 1] = this.data[i];
}
this.data[index] = e;
this.size++;
}
/**
* 向所有元素之后添加一个元素
* Time Complexity O(1)
* @param {E} e 要插入的元素
* @return {void}
*/
addLast(e: E): void {
this.add(this.size, e);
}
/**
* 向所有元素之前添加一个元素
* Time Complexity O(n)
* @param {E} e 要插入的元素
* @return {void}
*/
addFirst(e: E): void {
this.add(0, e);
}
/**
* 修改index索引位置元素为e
* Time Complexity O(1)
* @param {number} index 要插入元素的位置
* @param {E} e 要插入的元素
* @return {void}
*/
set(index: number, e: E) {
if (index < 0 || index >= this.size) {
throw new Error('Set failed. Index is illegal.');
}
this.data[index] = e;
}
/**
* 查找数组中是否含有元素e
* Time Complexity O(n)
* @param {E} e 要查找的元素
* @return {boolean}
*/
contains(e: E): boolean {
for (let i = 0; i < this.size; i++) {
if (e === this.data[i]) {
return true;
}
}
return false;
}
/**
* 查找数组中元素e所在的索引,如果不存在,则返回-1
* Time Complexity O(n)
* @param {E} e 要查找的元素
* @return {boolean}
*/
find(e: E): number {
for (let i = 0; i < this.size; i++) {
if (e === this.data[i]) {
return i;
}
}
return -1;
}
/**
* 从数组中删除index位置的元素,并且返回删除元素
* Time Complexity O(n)
* @param {number} index 要删除的元素位置的索引
* @return {E}
*/
remove(index: number): E {
if (index < 0 || index > this.size) {
throw new Error('Remove failed. index is illegal')
}
let ret: E = this.data[index];
for (let i = index + 1; i < this.size; i++) {
this.data[i - 1] = this.data[i];
}
this.size--;
this.data[this.size] = null;
// 当size == capacity / 4时,才将capacity减半。防止复杂度震荡
// data.length != 0 是因为不能常见capacity为0的数组
if (this.size === Math.floor(this.data.length / 4) && Math.floor(this.data.length / 2) !== 0) {
this.resize(Math.floor(this.data.length / 2));
}
return ret;
}
/**
* 删除数组中的最后一个元素
* Time Complexity O(1)
* @return {E}
*/
removeLast(): E {
return this.remove(this.size - 1);
}
/**
* 删除数组中的第一个元素
* Time Complexity O(n)
* @return {E}
*/
removeFirst(): E {
return this.remove(0);
}
/**
* 获取index索引的元素
* Time Complexity O(1)
* @param {number} index 要获取元素的索引
* @return {E}
*/
get(index: number): E {
if (index < 0 || index >= this.size) {
throw new Error('Get failed. Index is illegal...')
}
return this.data[index];
}
/**
* 获取数组中的第一个元素
* Time Complexity O(1)
* @return {E}
*/
getFirst() {
return this.get(0);
}
/**
* 获取数组中的最后一个元素
* Time Complexity O(1)
* @return {E}
*/
getLast() {
return this.get(this.size - 1);
}
/**
* 数组扩容,或者缩容操作
* Time Complexity O(n)
* @param {number} newCapacity 新的数组的容量
* @return {void}
*/
resize(newCapacity: number): void {
let newData: E[] = new Array(newCapacity);
for (let i = 0; i < this.size; i++) {
newData[i] = this.data[i];
}
this.data = newData;
}
/**
* 交换数组中的i, j两个元素
* Time Complexity O(1)
* @param {number} i 第i位置的元素
* @param {number} j 第j位置的元素
* @return {void}
*/
swap(i: number, j: number): void {
if (i < 0 || j < 0 || i >= this.size || j >= this.size) {
throw new Error('Index is illegal.');
}
let temp = this.data[i];
this.data[i] = this.data[j];
this.data[j] = temp;
}
toString(): string {
let res = '';
res += `Array: size = ${this.size}, capacity = ${this.getCapacity()}\n`;
res += '[';
for (let i = 0; i < this.size; i++) {
res += this.data[i];
if (i !== this.size - 1)
res += ', '
}
res += ']';
return res;
}
}