Java數組高頻考點實例分析

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;
    }
}

推薦力扣題目

1.刪除排序數組中的重複項

2.移動零

3.比較含退格的字符字串

4.有序數組的平方

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

以上是Java數組高頻考點實例分析的詳細內容。更多資訊請關注PHP中文網其他相關文章！