一.數(shù)組的概念
? ? 1. 數(shù)組定義
????????數(shù)組(Array)是一種線性結(jié)構(gòu)。它用一組連續(xù)的內(nèi)存空間，來存儲(chǔ)一組具有相同數(shù)據(jù)類型的數(shù)據(jù)。
? ?2. 數(shù)組的特點(diǎn)
????????①用來存儲(chǔ)一組類型相同的數(shù)據(jù)。
? ? ? ? ②在內(nèi)存中，分配連續(xù)的空間，數(shù)組創(chuàng)建時(shí)需要指定容量。因?yàn)閿?shù)組為了保持內(nèi)存的數(shù)據(jù)的連續(xù)性，所以會(huì)導(dǎo)致插入、刪除這兩個(gè)操作比較低效。
?? ? ? ?③數(shù)據(jù)類型[] 數(shù)組名 int[] arr = new int[10]; int[] arr2 = {1,2,3,4};
?? ? ? ?④訪問數(shù)組中的數(shù)據(jù)時(shí)，通過索引訪問，這也是數(shù)組的一大優(yōu)點(diǎn)，可以實(shí)現(xiàn)隨機(jī)訪問(通過索引，時(shí)間復(fù)雜度為O(1))，所以隨機(jī)訪問時(shí)，效率比較高。 所以，數(shù)組是適合查找操作的，但查找的時(shí)間復(fù)雜度并不是O(1),即使是排好序的數(shù)組，使用二分查找法，時(shí)間復(fù)雜度也是(logn)。
?? ? ? ?⑤索引從0開始，最大到數(shù)組長(zhǎng)度-1。索引從0開始，是因?yàn)樗饕?數(shù)組元素下標(biāo))，確切的來說應(yīng)該叫做偏移量，例如，arr[0]就表示偏移量為0的元素，也就是首地址。arr[k]就表示偏移量為k個(gè)type_size的位置。
?? ? ? ?⑥常見異常：NullPointException(空指針異常)、ArrayIndexOutOfBoundsException(數(shù)組索引越界異常)。
package com.gty.algo.lesson;
import java.util.Arrays;
public class ArrayDemo1 {
public static void main(String[] args) {
// 1.創(chuàng)建數(shù)組
int[] arr = {11, 9, 1, 2, 26, 12};
// 2.訪問指定位置的值
int num = arr[0]; //獲取第一個(gè)位置的值
System.out.println("num = " + num);
// 3.修改指定位置的值
arr[3] = 15;
System.out.println("修改后的值為：" + arr[3]);
// 4.遍歷數(shù)組
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
// 5.數(shù)組中的異常(數(shù)組索引越界異常)
System.out.println(arr[arr.length]); //ArrayIndexOutOfBoundsException
// 空指針異常
String[] s = new String[6];
System.out.println(Arrays.toString(s)); //[null, null, null, null, null, null]
System.out.println(s[0].length()); //NullPointerException
}
}
注：
- 數(shù)組是一段連續(xù)的內(nèi)存空間，用戶來存放具有相同數(shù)據(jù)類型的元素。
- 在定義數(shù)組時(shí)，需要注意數(shù)組的類型和長(zhǎng)度。類型決定了數(shù)組可以存儲(chǔ)的元素的種類，長(zhǎng)度定義了數(shù)組可以存儲(chǔ)的元素的數(shù)量。
- 在修改與訪問數(shù)組時(shí)，要注意數(shù)組的索引，避免出現(xiàn)數(shù)組索引越界異常。在修改數(shù)組中的元素的值時(shí)，要注意數(shù)組中元素的數(shù)據(jù)類型，避免出現(xiàn)類型不一致的錯(cuò)誤。
3.數(shù)組的遍歷
? ? ? ? 方法：for循環(huán)、for-each(增強(qiáng)for循環(huán))、調(diào)用toString方法 。
package com.gty.algo.lesson;
import java.util.Arrays;
public class ArrayDemo1 {
public static void main(String[] args) {
int[] arr = {11, 9, 1, 2, 26, 12};
/*
數(shù)組的遍歷
*/
//1.for循環(huán)
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
//2.for-each(增強(qiáng)for循環(huán))
for (int x:arr) {
System.out.print(x + " ");
}
System.out.println();
//調(diào)用toString方法
System.out.println(Arrays.toString(arr));
}
}?二.封裝數(shù)組
? ? ? ? 基于java提供給我們的數(shù)組，進(jìn)行二次封裝，我們可以自己去寫一個(gè)我們自己的數(shù)組(動(dòng)態(tài)數(shù)組)去實(shí)現(xiàn)數(shù)組的各種基本功能。
1.封裝數(shù)組
主要功能：
? ? ? ? 添加元素，獲取元素，查看當(dāng)前數(shù)組中元素的個(gè)數(shù)，獲取容積，修改元素，數(shù)組擴(kuò)容，判空，查詢指定元素，刪除指定位置的元素。
package com.gty.algo.lesson.array;
// 支持泛型
public class MyArray<T> {
private T[] arr;
private int size;
private int capacity; //容積
// 構(gòu)造方法
public MyArray(int capacity) {
// 入?yún)⑴袛? if (capacity <= 0) {
throw new IllegalArgumentException("輸入容積異常！");
}
this.capacity = capacity;
this.size = 0;
this.arr = (T[]) new Object[this.capacity];
}
// 獲取元素個(gè)數(shù)
public int getSize() {
return this.size;
}
// 獲取容積
public int getCapacity() {
return this.capacity;
}
// 添加元素
public void add(T item) {
this.arr[this.size] = item;
this.size++;
}
// 向指定位置添加元素
public void addValueByIndex(int index, T value) {
if (index < 0 || index > this.size) {
throw new IllegalArgumentException("索引異常！");
}
if (this.size == this.capacity) {
resize(this.capacity * 2);
}
for (int i = this.size - 1; i >= index; i--) {
this.arr[i + 1] = this.arr[i];
}
this.arr[index] = value;
this.size++;
}
// 擴(kuò)容
private void resize(int newCapacity) {
T[] newArr = (T[]) new Object[newCapacity];
for (int i = 0; i < this.size; i++) {
newArr[i] = this.arr[i];
}
// 改變?nèi)萜髋c容積
this.arr = newArr;
this.capacity = newCapacity;
}
// 判空
public boolean isEmpty() {
return this.size == 0;
}
// 修改元素
public void modifyValueByIndex(int index, T value) {
// 入?yún)⑴袛? if (index < 0 || index > capacity) {
throw new IllegalArgumentException("索引異常！");
}
this.arr[index] = value;
}
// 獲取指定位置的值
public T getValueByIndex(int index) {
// 入?yún)⑴袛? if (index < 0 || index > capacity) {
throw new IllegalArgumentException("索引異常！");
}
return this.arr[index];
}
// 查詢指定的值在數(shù)組中是否存在，存在返回索引，不存在返回-1
public int containsValue(T value) {
for (int i = 0; i < this.size; i++) {
if (value.equals(this.arr[i])) {
return i;
}
}
return -1;
}
// 刪除指定位置的元素
public T deleteValueByIndex(int index) {
// 入?yún)⑴袛? if (index < 0 || index > capacity) {
throw new IllegalArgumentException("索引異常");
}
// 1.找到刪除的位置的元素
T deValue = this.arr[index];
// 2.將刪除元素之后的元素前移
for (int j = index + 1; j < this.size; j++) {
this.arr[j - 1] = this.arr[j];
}
this.size--;
// 判斷是否縮容
if (this.size <= this.capacity / 4 && this.capacity / 2 > 0) {
resize(this.capacity / 2);
}
return deValue;
}
// 重寫toString方法，用于數(shù)組打印
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("{");
for (int i = 0; i < this.size; i++) {
sb.append(this.arr[i]);
if (i < this.size - 1) {
sb.append(",");
}
}
sb.append("}");
return sb.toString();
}
}?2.例題介紹
? ? ? ? 兩數(shù)之和(1. 兩數(shù)之和 - 力扣（LeetCode）)文章來源：http://www.zghlxwxcb.cn/news/detail-824673.html
- ?題解：可以利用Map，將數(shù)組中的值和其對(duì)應(yīng)的索引以鍵值對(duì)的方式存放在Map中。遍歷數(shù)組，當(dāng)發(fā)現(xiàn)target - nums[i](這是解決本題的重點(diǎn)思想，將兩數(shù)之和轉(zhuǎn)換為兩數(shù)之差(值1 - 值2 = 目標(biāo)值 即為，目標(biāo)值 - 值1 = 值2))在Map中，說明找到了目標(biāo)值，返回target - nums[i]的下標(biāo)和i即可?；谝陨纤枷?，在向Map中存放鍵值對(duì)時(shí)，可以將數(shù)組中元素的值作為鍵，元素在數(shù)組中的索引作為值存放在Map中，方便我們獲取索引。
- 代碼實(shí)現(xiàn)
package com.gty.algo.subject;
import java.util.Arrays;
import java.util.HashMap;
public class LeetCode_01 {
public int[] twoSum(int[] nums, int target) {
// 入?yún)⑴袛? if(nums == null || nums.length < 2){
return null;
}
// 利用Map，將數(shù)組中的值和其對(duì)應(yīng)的索引以鍵值對(duì)的方式存放起來，可以將值作為Map中的鍵，索引作為值,
HashMap<Integer, Integer> map = new HashMap<>();
// 遍歷數(shù)組，求數(shù)組中兩數(shù)之和等于目標(biāo)值，即求目標(biāo)值 - 值1 = 值2，
for (int i = 0; i < nums.length; i++) {
int temp = target - nums[i];
if(map.containsKey(temp)){ //判斷值是否存在
return new int[]{map.get(temp),i}; //map.get(temp)---通過key獲取key對(duì)應(yīng)的value
}else{
map.put(nums[i],i); //向Map中添加元素
}
}
return null;
}
public static void main(String[] args) {
int [] nums = {2,7,11,15};
LeetCode_01 leetCode_01 = new LeetCode_01();
int [] res = leetCode_01.twoSum(nums,9);
System.out.println(Arrays.toString(res)); //[0, 1]
}
}?
文章來源地址http://www.zghlxwxcb.cn/news/detail-824673.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)(數(shù)組)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
