Java 陣列高頻考點分析講解

2022-04-02 19:00:20

1、陣列理論基礎

陣列是存放在連續記憶體空間上的相同型別資料的集合，可以通過下標索引的方式獲取到下標下對應的資料。

舉個栗子（字元陣列）~

可以看到：

1、陣列的下標從0開始

2、陣列在記憶體中的地址是連續的

所以在刪除元素時，只能用覆蓋的方式進行。

例如，要刪除下標為2的元素~ 就需要將從2之後的元素依次移到前一個，覆蓋掉要刪除的元素。

所以刪除元素並不是將該元素的空間釋放了，而是將後面的元素移到前面，覆蓋掉要刪除的元素，然後將陣列的長度減去1，就能得到一個看似新的陣列。

在java中，二維陣列的儲存方式如下：

2、常見考點

1.二分查詢

力扣題目連結: 二分查詢

這道題目的前提是有序陣列，因為一旦有重複元素，使用二分查詢法返回的元素下標可能不是唯一的，這些都是使用二分法的前提條件。

二分查詢思想是：

陣列有序的前提下（假設升序），如果陣列中間的值大於要查詢的值，那麼要查詢的元素就不可能在後半部分，因為後半部分的值都大於中間的值，所以通過第一次比較，就可以將範圍縮小一半，後面同理，即時間複雜度降到了O(logN)，效率大大提高，當題目中要求查詢元素的時間複雜度為O(logN)時，首先想一想是否能用二分呢？

class Solution {
    public int search(int[] nums, int target) {
        // 避免當 target 小於nums[0] nums[nums.length - 1]時多次迴圈運算
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
        }
        return -1;
    }
}

2.移除元素

有的同學可能說了，多餘的元素，刪掉不就得了？但是要知道陣列的元素在記憶體地址中是連續的，不能單獨刪除陣列中的某個元素，只能覆蓋。

例如：給你一個陣列和一個val值，要求刪除陣列中等於val值的元素，怎麼做呢？

思路1：暴力法

我們可以使用兩個for迴圈，當遍歷到等於val值的元素時，就將後面的元素整體往前移一個覆蓋掉要刪除的元素，但是這種做法顯然時間複雜度太高。

class Solution {
    public int removeElement(int[] nums, int val) {
        int size = nums.length;
        for (int i = 0; i < size;i++ ) {
            if (nums[i] == val) { // 發現需要移除的元素，就將陣列後面集體向前移動一位
                for (int j = i + 1; j < size; j++) {
                    nums[j - 1] = nums[j];
                }
                i--; // 因為下標i以後的數值都向前移動了一位，所以i也向前移動一位
                size--;
            }
        }
        return size;
    }
}

思路2：雙指標法

分別設設一個快慢指標，slow fast ，兩者一起走，當慢指標遇到要刪除的元素時停下，等待著被刪除（覆蓋）；當快指標走到要被留下的元素時，將快指標的元素賦值給慢指標，然後兩指標同時向後走，直到快指標遍歷完整個陣列。

可以這麼理解：定義陣列的新長度newLength ，從0開始，定義一個快指標遍歷陣列 fast，當fast走到要被留下的元素時，說明該元素應該被新增到新陣列中（即被新增到newLength 下標，這裡相當於 newLength 之前的部分陣列看做要返回的新陣列，相當於往這個新陣列裡插入元素）。

class Solution {
    public int removeElement(int[] nums, int val) {
        int fast = 0;// 定義一個快指標遍歷陣列
        int newLength = 0;// 定義新的陣列長度
        while(fast < nums.length){
            if(nums[fast] != val){
                nums[newLength++] = nums[fast];
            }
            fast++;
        }
        return newLength;
    }
}

推薦力扣題目

其他常見陣列的考點很多都是以這兩點為基礎，無非就是對陣列增刪改查，將陣列的查詢和刪除掌握了，就可以開始刷題啦。

到此這篇關於Java 陣列高頻考點分析講解的文章就介紹到這了,更多相關Java 陣列內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

Java 陣列高頻考點分析講解

目錄

1、陣列理論基礎

2、常見考點

1.二分查詢

2.移除元素

熱門文章