Java真題實(shí)練掌握哈希表的使用

更新時(shí)間：2022年07月21日 09:30:38 作者：風(fēng)鈴聽雨~

哈希表是一種根據(jù)關(guān)鍵碼去尋找值的數(shù)據(jù)映射結(jié)構(gòu)，該結(jié)構(gòu)通過把關(guān)鍵碼映射的位置去尋找存放值的地方，說起來可能感覺有點(diǎn)復(fù)雜，我想我舉個(gè)例子你就會(huì)明白了，最典型的的例子就是字典

1.多數(shù)元素

題目描述

思路詳解

這個(gè)思路比較簡(jiǎn)單，先排序，排序過后遍歷如果后一個(gè)等于前一個(gè)輸出就好

代碼與結(jié)果

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

2.數(shù)組中的k-diff數(shù)對(duì)

題目描述

思路詳解

這里我們采用排序和雙指針的方法。

我們首先把數(shù)組進(jìn)行排序，然后利用前后兩個(gè)指針遍歷數(shù)組，找出符合條件的組合。

注意：這里我們我們要注意結(jié)果的重復(fù)，也要注意兩個(gè)指針前進(jìn)的條件。

代碼與結(jié)果

class Solution {
    public int findPairs(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length, y = 0, res = 0;
        for (int x = 0; x < n; x++) {
            if (x == 0 || nums[x] != nums[x - 1]) {
                while (y < n && (nums[y] < nums[x] + k || y <= x)) {
                    y++;
                }
                if (y < n && nums[y] == nums[x] + k) {
                    res++;
                }
            }
        }
        return res;
    }
}

3.缺失的第一個(gè)正數(shù)

題目描述

思路詳解

這一題屬于比較困難的題目。

我們首先想到的就是排序然后遍歷，可是這違背了題目時(shí)間復(fù)雜度是常數(shù)的要求。

那么我們用哈希表進(jìn)行存儲(chǔ)遍歷呢，顯然這也超出了時(shí)間復(fù)雜度的限制。

小編也是參考了題解，現(xiàn)在就來用自己的話說說這一題的做法吧.

對(duì)數(shù)組進(jìn)行遍歷，對(duì)于遍歷到的數(shù) x，如果它在[1,N] 的范圍內(nèi)，那么就將數(shù)組中的第x−1 個(gè)位置（注意：數(shù)組下標(biāo)從 0 開始）打上「標(biāo)記」。在遍歷結(jié)束之后，如果所有的位置都被打上了標(biāo)記，那么答案是N+1，否則答案是最小的沒有打上標(biāo)記的位置加 1。

這里是采用了仿哈希表的結(jié)構(gòu)。

代碼與結(jié)果

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
        for (int i = 0; i < n; ++i) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
    }
}

到此這篇關(guān)于Java真題實(shí)練掌握哈希表的使用的文章就介紹到這了,更多相關(guān)Java哈希表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: