一、使用java中的數組 數組:把數據碼成一排進行存放 在元素前面添加一個新元素 四、數組中查詢元素和修改元素 還是在上面的類中寫方法,這裡重寫toString方法,用於查詢元素 把前面寫的功能進行測試 說明還是成功的,由於int類型太單調,之後都將使用泛型來進行操作 七、動態數組 由於數組是由限制 ...
一、使用java中的數組
數組:把數據碼成一排進行存放
public class array {
public static void main(String[] args ){
//定義數組指定長度
int[] arr = new int[10];
for (int i = 0; i<arr.length; i++)
arr[i] = i;
//
int[] scores = new int[]{100,99,66};
for (int i = 0; i<scores.length; i++)
System.out.println(scores[i]);
// 數組可遍歷
scores[0] = 98;
for (int score: scores)
System.out.println(score);
}
}
二、二次封裝屬於我們自己的數組
數組最大的優點:快速查詢 score[2]
數組最好應用於“索引有語意”的情況
但並非所有有語意的索引都適合用於數組,例如身份證號
數組也可以處理“索引沒有語意”的情況,這裡主要處理“索引沒有語義”的情況數組的使用
public class array {
private int[] data;
private int size;
// 構造函數,傳入數組的容量capacity構造array
public array(int capacity){
data = new int[capacity];
size = 0;
}
// 無參數的構造函數,預設數組容量capaciay=10
public array(){
this(10);
}
// 獲取數組中的元素個數
public int getSize(){
return size;
}
// 獲取數組的容量
public int getCapacity(){
return data.length;
}
// 判斷數組是否為空
public boolean isEmpty(){
return size == 0;
}
}
三、向數組添加元素
向數組末尾添加元素,還是在上面的類中添加方法
// 向所有元素後添加一個新元素
public void addList(int e){
// 如果元素的個數等於數組的容量,那麼拋出異常
if (size == data.length)
throw new IllegalArgumentException("AddLast failed. array is full");
data[size] = e;
size++;
}
指定位置添加元素
// 在第index個位置插入一個新元素e
public void add(int index,int e){
if (size == data.length)
throw new IllegalArgumentException("Add failed. array is full");
if (index < 0 || index > size){
throw new IllegalArgumentException("Add failed. array is full");
}
for (int i = size - 1; i >= index; i--){
data[i+1] = data[i];
}
data[index] = e;
size++;
}
在元素前面添加一個新元素
// 在所有元素前添加一個新元素
public void addFirst(int e){
add(0,e);
}
四、數組中查詢元素和修改元素
還是在上面的類中寫方法,這裡重寫toString方法,用於查詢元素
@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();
}
獲取元素以及修改元素
// 獲取index索引位置的元素
int get(int index){
if (index < 0 || index >= size)
throw new IllegalArgumentException("GET failed. array is full");
return data[index];
}
// 修改index索引位置的元素e
void set (int index,int e){
if (index < 0 || index >= size)
throw new IllegalArgumentException("set failed. array is full");
data[index] = e;
}
把前面寫的功能進行測試
public class Main {
public static void main(String[] args ){
array arr = new array(20);
for (int i = 0 ; i < 10 ; i++){
arr.addList(i);
}
System.out.println(arr);
// 索引為1的位置添加100
arr.add(1,100);
System.out.println(arr);
// 開始添加-1
arr.addFirst(-1);
System.out.println(arr);
}
}
// 列印結果
array: size = 10 , capacity = 20
[0,1,2,3,4,5,6,7,8,9]
array: size = 11 , capacity = 20
[0,100,1,2,3,4,5,6,7,8,9]
array: size = 12 , capacity = 20
[-1,0,100,1,2,3,4,5,6,7,8,9]
五、包含,搜索和刪除
還是在上面的類中寫方法,包含
// 查找數組中是否有元素e
public boolean contains(int e){
for (int i = 0 ; i < size ; i++){
if (data[i] == e){
return true;
}
}
return false;
}
搜索
// 查找數組中元素e所在的索引,如果元素不存在,返回-1
public int find(int e){
for (int i = 0 ; i < size ; i++){
if (data[i] == e){
return i;
}
}
return -1;
}
刪除
// 從數組中刪除index位置的元素,返回刪除的元素
public int remove(int index){
if (index < 0 || index >= size)
throw new IllegalArgumentException("Remove failed");
int ret = data[index];
for (int i = index + 1 ; i < size ; i++)
data [ i - 1] = data[i];
// 這個地方需要註意
size --;
return ret;
}
// 從數組中刪除第一個元素,返回刪除的元素
public int removeFirst(){
return remove(0);
}
// 從數組中刪除最後一個元素,返回刪除的元素
public int removeLast(){
return remove(size - 1);
}
// 從數組中刪除元素e
public void removeElement(int e){
int index = find(e);
if (index != -1){
remove(index);
}
}
進行測試
public class Main {
public static void main(String[] args ){
array arr = new array(20);
for (int i = 0 ; i < 10 ; i++){
arr.addList(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(4);
System.out.println(arr);
arr.removeFirst();
arr.removeLast();
System.out.println(arr);
}
}
array: size = 10 , capacity = 20
[0,1,2,3,4,5,6,7,8,9]
array: size = 11 , capacity = 20
[0,100,1,2,3,4,5,6,7,8,9]
array: size = 12 , capacity = 20
[-1,0,100,1,2,3,4,5,6,7,8,9]
array: size = 11 , capacity = 20
[-1,0,1,2,3,4,5,6,7,8,9]
array: size = 10 , capacity = 20
[-1,0,1,2,3,5,6,7,8,9]
array: size = 8 , capacity = 20
[0,1,2,3,5,6,7,8]
基本功能已經實現,但是還是有很多需要完善的地方。
六、使用泛型
- 讓我們的數據結構可以放置任何的數據類型
- 不可以是基本數據類型,只能是類對象:boolean、byte、chat、short、int、long、float、double
- 每個基本數據類型都有對應的包裝類:Boolean、Byte、Chat、Short、Int、Long、Float、Double
- 下麵還是針對上面的進行修改,由於使用了泛型,這裡將array類全部放在這裡方便大家觀看
public class array<E> {
// 數據類型由之前的int改成現在的
private E[] data;
private int size;
// 構造函數,傳入數組的容量capacity構造array
// 這裡使用了強制類型轉化
public array(int capacity){
data = (E[]) new Object[capacity];
size = 0;
}
// 無參數的構造函數,預設數組容量capaciay=10
public array(){
this(10);
}
// 獲取數組中的元素個數
public int getSize(){
return size;
}
// 獲取數組的容量
public int getCapacity(){
return data.length;
}
// 判斷數組是否為空
public boolean isEmpty(){
return size == 0;
}
// 向所有元素後添加一個新元素,轉入參數類型改變
public void addLast(E e){
// 如果元素的個數等於數組的容量,那麼拋出異常
if (size == data.length)
throw new IllegalArgumentException("AddLast failed. array is full");
data[size] = e;
size++;
}
// 在所有元素前添加一個新元素,轉入參數類型改變
public void addFirst(E e){
add(0,e);
}
// 在第index個位置插入一個新元素e,轉入參數類型改變
public void add(int index,E e){
if (size == data.length)
throw new IllegalArgumentException("Add failed. array is full");
if (index < 0 || index > size){
throw new IllegalArgumentException("Add failed. array is full");
}
for (int i = size - 1; i >= index; i--){
data[i+1] = data[i];
}
data[index] = e;
size++;
}
@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();
}
// 獲取index索引位置的元素,返回類型改變
E get(int index){
if (index < 0 || index >= size)
throw new IllegalArgumentException("GET failed. array is full");
return data[index];
}
// 修改index索引位置的元素e,轉入參數類型改變
void set (int index,E e){
if (index < 0 || index >= size)
throw new IllegalArgumentException("set failed. array is full");
data[index] = e;
}
// 查找數組中是否有元素e
public boolean contains(E e){
for (int i = 0 ; i < size ; i++){
if (data[i] .equals(e) ){
return true;
}
}
return false;
}
// 查找數組中元素e所在的索引,如果元素不存在,返回-1,轉入參數類型改變
public int find(E e){
for (int i = 0 ; i < size ; i++){
if (data[i] .equals(e) ){
return i;
}
}
return -1;
}
// 從數組中刪除index位置的元素,返回刪除的元素,返回類型改變
public E remove(int index){
if (index < 0 || index >= size)
throw new IllegalArgumentException("Remove failed");
E ret = data[index];
for (int i = index + 1 ; i < size ; i++)
data [ i - 1] = data[i];
size --;
// data[size] = null; // loitering objects
return ret;
}
// 從數組中刪除第一個元素,返回刪除的元素
public E removeFirst(){
return remove(0);
}
// 從數組中刪除最後一個元素,返回刪除的元素
public E removeLast(){
return remove(size - 1);
}
// 從數組中刪除元素e
public void removeElement(E e){
int index = find(e);
if (index != -1){
remove(index);
}
}
}
為了進行測試,從新建一個Student類來進行測試,這樣就可以使用任意類型的數據
public class Student {
private String name;
private int score;
public Student(String studentName, int studentScore){
name = studentName;
score = studentScore;
}
@Override
public String toString() {
return String.format("Student(name: %s , score: %d)\n",name,score);
}
public static void main(String[] args){
// 使用泛型
array<Student> arr = new array<>();
arr.addLast(new Student("Alice",100));
arr.addLast(new Student("Bob",88));
arr.addLast(new Student("Char",66));
System.out.println(arr);
}
}
public class Student {
private String name;
private int score;
public Student(String studentName, int studentScore){
name = studentName;
score = studentScore;
}
@Override
public String toString() {
return String.format("Student(name: %s , score: %d)\n",name,score);
}
public static void main(String[] args){
// 使用泛型
array<Student> arr = new array<>();
arr.addLast(new Student("Alice",100));
arr.addLast(new Student("Bob",88));
arr.addLast(new Student("Char",66));
System.out.println(arr);
}
}
array: size = 3 , capacity = 10
[Student(name: Alice , score: 100)
,Student(name: Bob , score: 88)
,Student(name: Char , score: 66)
]
說明還是成功的,由於int類型太單調,之後都將使用泛型來進行操作
七、動態數組
由於數組是由限制的,在用戶不知道數據的個數的時候,容易拋出異常,這個時候就要使用動態數組,而不用再考慮數據的個數
具體的實現,還是在array類中
// 動態數組
private void resize(int newCapacity){
// 使用泛型,強制類型轉換
E[] newData = (E[])new Object[newCapacity];
// 把之前數組中的數據傳到新的數組中
for (int i = 0 ; i < size ; i ++){
newData[i] = data[i];
}
//新的數組再指向到原來的數組,狸貓換太子
data = newData;
}
把添加元素的方法進行改寫,
public void add(int index,E e){
// 如果數組已經滿了
if (size == data.length)
// throw new IllegalArgumentException("Add failed. array is full");
// 調用動態數組,擴容到之前容量的二倍
resize(2 * data.length);
if (index < 0 || index > size){
throw new IllegalArgumentException("Add failed. array is full");
}
for (int i = size - 1; i >= index; i--){
data[i+1] = data[i];
}
data[index] = e;
size++;
}
把刪除元素的方法也進行改寫
public E remove(int index){
if (index < 0 || index >= size)
throw new IllegalArgumentException("Remove failed");
E ret = data[index];
for (int i = index + 1 ; i < size ; i++)
data [ i - 1] = data[i];
size --;
// data[size] = null; // loitering objects
// 如果數組中剩餘的數量是數組長度的二倍,那麼就把數組的長度減半
if (size == data.length / 2)
resize(data.length / 2);
return ret;
}
進行測試
public class Main {
public static void main(String[] args ){
// int類型的包裝類
array<Integer> arr = new array<>(5);
for (int i = 0 ; i < 5 ; 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(4);
System.out.println(arr);
arr.removeFirst();
arr.removeLast();
System.out.println(arr);
}
}
array: size = 5 , capacity = 5
[0,1,2,3,4]
當數據多的時候,自動擴容的之前的兩倍
array: size = 6 , capacity = 10
[0,100,1,2,3,4]
array: size = 7 , capacity = 10
[-1,0,100,1,2,3,4]
array: size = 6 , capacity = 10
[-1,0,1,2,3,4]
當數據少的時候,自動縮少兩倍
array: size = 5 , capacity = 5
[-1,0,1,2,3]
array: size = 3 , capacity = 5
[0,1,2]
這樣就基本實現了動態的數組
八、簡單的時間複雜度分析
- O(1),O(n),O(lgn),O(nlogn),O(n^2)
- 大O描述的是演算法的運行時間和輸入數據之間的關係
public static int sum(int[] nums){
int sun = 0;
for(int num: nums) sum += num;
return sum;
}
這裡演算法是O(n),這裡n是nums中元素的個數
也就是說這個演算法運行的時間的多少和這裡的nums中元素的個數呈線性關係,也就是nums中的個數越多時間就越多
- 為什麼要用大O,叫做O(n)?忽略常數,實際時間(線性)
$$
T = c1*n + c2
$$
具體分析演算法的時候就直接忽略常數,漸進時間複雜度,描述n趨近於無窮的情況
T = 2*n + 2 | O(n) |
T = 2000*n + 1000 | O(n) |
T = nn1 + 0 | O(n^2) |
T = 2nn + 300*n + 10 | O(n^2) |
其中n的冪數越大性能越差
分析動態數組的時間複雜度
向數組頭添加元素的時候,要把數組中的每一個元素往後面移動,所以是O(n),整體來看,通常做最壞的打算,也是O(n),添加的還有註意resize方法
添加操作 | O(n) |
---|---|
addLast(e) | O(1) |
addFirst(e) | O(n) |
add(index,e) | O(n/2) = O(n) |
resize | O(n) |
刪除操作和上面的一樣,也是做最壞的打算,也是O(n),刪除時還要註意resize方法
刪除操作 | O(n) |
---|---|
removeLast(e) | O(1) |
removeFirst(e) | O(n) |
remove(index,e) | O(n/2) = O(n) |
修改操作,這個是最簡單的,O(1)
修改操作 | O(1) |
---|---|
set(index,e) | O(1) |
查找操作,也是O(n)
查找操作 | O(n) |
---|---|
get(index) | O(1) |
contains(e) | O(n) |
find(e) | O(n) |
總結
增 | O(n) |
刪 | O(n) |
改 | 已知索引O(1),未知索引O(n) |
查 | 已知索引O(1),未知索引O(n) |
註意:對於增和刪,如果只對最後一個元素操作依然是O(n)?,因為resize方法?
九、均攤複雜度和防止複雜度的震蕩
- resize的複雜度分析
從最壞的方面來看,addLast(e)的複雜度是O(1),如果此時數組容量不夠需要擴容的時候就要調用resize方法,但是resize方法的複雜度是O(n),所以綜合來說addLast(e)的複雜度是O(n),但是也不是每一次添加就會擴容,所以用最壞的來分析有點不合理,這裡用到下麵的知識了
假設當前的capacity = 8 ,並且每一次添加操作都使用addLast
$$
1+1+1+1+1+1+1+1+8+1
$$
9次addLast操作,觸發resize,總共進行了17次的基本操作,9次添加,8次轉移,
平均來說也就是每次addLast操作,進行了大約兩次基本操作
假設capacity = n,n+1次addLast,觸發resize,總共進行2n+1次基本操作
平均,每次addLast操作,進行2次基本操作
這樣均攤計算,時間複雜程度是O(1)
所以在這個例子中,均攤計算,比計算最壞情況有意義
- 均攤複雜度
addLast的均攤複雜度是O(1)
同理,removeLast的均攤複雜度也是O(1)
- 複雜度的震蕩
但是,我們同時來看addLast和removeLast操作
當capacity = n時,調用addLast,這裡進行擴容,複雜度O(n),然後執行removeLast,進行縮容,複雜度也是O(n),如此迴圈,複雜度就一直是O(n)了
出現問題的原因:removeLast是resize過於著急(Eager),不必一下子就縮容
解決方案:Lazy,當數據是總長度的1/4時進行縮容,縮容還是變回原來的一半
當size == capacity /4 時,才將capacity減半
通過這樣的方法,就解決了複雜度震蕩的問題
下麵用代碼實現,還是在array類中修改,把remove方法改寫就可以了,
public E remove(int index){
if (index < 0 || index >= size)
throw new IllegalArgumentException("Remove failed");
E ret = data[index];
for (int i = index + 1 ; i < size ; i++)
data [ i - 1] = data[i];
size --;
// data[size] = null; // loitering objects
// 這裡等於1/4的才進行縮容,但是還要註意長度除於2不能等於0
if (size == data.length / 4 && data.length / 2 != 0)
resize(data.length / 2);
return ret;
}