1、數(shù)組理論基礎(chǔ)

數(shù)組是存放在連續(xù)內(nèi)存空間上的相同類型數(shù)據(jù)的集合，可以通過(guò)下標(biāo)索引的方式獲取到下標(biāo)下對(duì)應(yīng)的數(shù)據(jù)。

舉個(gè)栗子（字符數(shù)組）~

可以看到：

1、數(shù)組的下標(biāo)從0開(kāi)始

2、數(shù)組在內(nèi)存中的地址是連續(xù)的

所以在刪除元素時(shí)，只能用覆蓋的方式進(jìn)行。

例如，要?jiǎng)h除下標(biāo)為2的元素~ 就需要將從2之后的元素依次移到前一個(gè)，覆蓋掉要?jiǎng)h除的元素。

所以刪除元素并不是將該元素的空間釋放了，而是將后面的元素移到前面，覆蓋掉要?jiǎng)h除的元素，然后將數(shù)組的長(zhǎng)度減去1，就能得到一個(gè)看似新的數(shù)組。

在java中，二維數(shù)組的存儲(chǔ)方式如下：

2、常見(jiàn)考點(diǎn)

1.二分查找

力扣題目鏈接: 二分查找

這道題目的前提是有序數(shù)組，因?yàn)橐坏┯兄貜?fù)元素，使用二分查找法返回的元素下標(biāo)可能不是唯一的，這些都是使用二分法的前提條件。

二分查找思想是：

數(shù)組有序的前提下（假設(shè)升序），如果數(shù)組中間的值大于要查找的值，那么要查找的元素就不可能在后半部分，因?yàn)楹蟀氩糠值闹刀即笥谥虚g的值，所以通過(guò)第一次比較，就可以將范圍縮小一半，后面同理，即時(shí)間復(fù)雜度降到了O(logN)，效率大大提高，當(dāng)題目中要求查找元素的時(shí)間復(fù)雜度為O(logN)時(shí)，首先想一想是否能用二分呢？

class Solution {
    public int search(int[] nums, int target) {
        // 避免當(dāng) target 小于nums[0] nums[nums.length - 1]時(shí)多次循環(huán)運(yùn)算
        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.移除元素

有的同學(xué)可能說(shuō)了，多余的元素，刪掉不就得了？但是要知道數(shù)組的元素在內(nèi)存地址中是連續(xù)的，不能單獨(dú)刪除數(shù)組中的某個(gè)元素，只能覆蓋。

例如：給你一個(gè)數(shù)組和一個(gè)val值，要求刪除數(shù)組中等于val值的元素，怎么做呢？

思路1：暴力法

我們可以使用兩個(gè)for循環(huán)，當(dāng)遍歷到等于val值的元素時(shí)，就將后面的元素整體往前移一個(gè)覆蓋掉要?jiǎng)h除的元素，但是這種做法顯然時(shí)間復(fù)雜度太高。

class Solution {
    public int removeElement(int[] nums, int val) {
        int size = nums.length;
        for (int i = 0; i < size;i++ ) {
            if (nums[i] == val) { // 發(fā)現(xiàn)需要移除的元素，就將數(shù)組后面集體向前移動(dòng)一位
                for (int j = i + 1; j < size; j++) {
                    nums[j - 1] = nums[j];
                }
                i--; // 因?yàn)橄聵?biāo)i以后的數(shù)值都向前移動(dòng)了一位，所以i也向前移動(dòng)一位
                size--;
            }
        }
        return size;
    }
}

思路2：雙指針?lè)?/p>

分別設(shè)設(shè)一個(gè)快慢指針，slow fast ，兩者一起走，當(dāng)慢指針遇到要?jiǎng)h除的元素時(shí)停下，等待著被刪除（覆蓋）；當(dāng)快指針走到要被留下的元素時(shí)，將快指針的元素賦值給慢指針，然后兩指針同時(shí)向后走，直到快指針遍歷完整個(gè)數(shù)組。

可以這么理解：定義數(shù)組的新長(zhǎng)度newLength ，從0開(kāi)始，定義一個(gè)快指針遍歷數(shù)組 fast，當(dāng)fast走到要被留下的元素時(shí)，說(shuō)明該元素應(yīng)該被添加到新數(shù)組中（即被添加到newLength 下標(biāo)，這里相當(dāng)于 newLength 之前的部分?jǐn)?shù)組看做要返回的新數(shù)組，相當(dāng)于往這個(gè)新數(shù)組里插入元素）。

class Solution {
    public int removeElement(int[] nums, int val) {
        int fast = 0;// 定義一個(gè)快指針遍歷數(shù)組
        int newLength = 0;// 定義新的數(shù)組長(zhǎng)度
        while(fast < nums.length){
            if(nums[fast] != val){
                nums[newLength++] = nums[fast];
            }
            fast++;
        }
        return newLength;
    }
}

推薦力扣題目

1.刪除排序數(shù)組中的重復(fù)項(xiàng)

2.移動(dòng)零

3.比較含退格的字符串

4.有序數(shù)組的平方

其他常見(jiàn)數(shù)組的考點(diǎn)很多都是以這兩點(diǎn)為基礎(chǔ)，無(wú)非就是對(duì)數(shù)組增刪改查，將數(shù)組的查找和刪除掌握了，就可以開(kāi)始刷題啦。

到此這篇關(guān)于Java 數(shù)組高頻考點(diǎn)分析講解的文章就介紹到這了,更多相關(guān)Java 數(shù)組內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論