Java真題實練掌握哈希表的使用

更新時間：2022年07月21日 09:30:38 作者：風鈴聽雨~

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

1.多數(shù)元素

題目描述

思路詳解

這個思路比較簡單，先排序，排序過后遍歷如果后一個等于前一個輸出就好

代碼與結(jié)果

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

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

題目描述

思路詳解

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

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

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

代碼與結(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.缺失的第一個正數(shù)

題目描述

思路詳解

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

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

那么我們用哈希表進行存儲遍歷呢，顯然這也超出了時間復雜度的限制。

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

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

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

您可能感興趣的文章: