Java真题实练掌握哈希表的使用

2024-10-09 09:13:04

1.多数元素

题目描述

思路详解

这个思路比较简单，先排序，排序过后遍历如果后一个等于前一个输出就好

代码与结果

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

2.数组中的k-diff数对

题目描述

思路详解

这里我们采用排序和双指针的方法。

我们首先把数组进行排序，然后利用前后两个指针遍历数组，找出符合条件的组合。

注意：这里我们我们要注意结果的重复，也要注意两个指针前进的条件。

代码与结果

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.缺失的第一个正数

题目描述

思路详解

这一题属于比较困难的题目。

我们首先想到的就是排序然后遍历，可是这违背了题目时间复杂度是常数的要求。

那么我们用哈希表进行存储遍历呢，显然这也超出了时间复杂度的限制。

小编也是参考了题解，现在就来用自己的话说说这一题的做法吧.

对数组进行遍历，对于遍历到的数 x，如果它在[1,N] 的范围内，那么就将数组中的第x−1 个位置（注意：数组下标从 0 开始）打上「标记」。在遍历结束之后，如果所有的位置都被打上了标记，那么答案是N+1，否则答案是最小的没有打上标记的位置加 1。

这里是采用了仿哈希表的结构。

代码与结果

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哈希表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

一文彻底搞定Java哈希表和哈希冲突

一.什么是哈希表? 哈希表也叫散列表,它是基于数组的.这间接带来了一个优点:查找的时间复杂度为 O(1).当然,它的插入时间复杂度也是 O(1).还有一个缺点:数组创建后扩容成本较高. 哈希表中有一个"主流"思想:转换.一个重要的概念是将「键」或「关键字」转换成数组下标.这由"哈希函数"完成. 二.什么是哈希函数? 由上,其作用就是将非 int 的键/关键字转化为 int 的值,使可以用来做数组下标. 比如,HashMap 中就这样实现了哈希函数: static f
Java实现哈希表的基本功能

一.哈希表头插法放入元素 /** * user:ypc: * date:2021-05-20; * time: 11:05; */ public class HashBuck { class Node { public int key; int value; Node next; Node(int key, int value) { this.key = key; this.value = value; } } public int usedSize; public Node[] array;
带你了解Java数据结构和算法之哈希表

目录 1.哈希函数的引入 ①.把数字相加 ②.幂的连乘 2.冲突 3.开放地址法 ①.线性探测 ②.装填因子 ③.二次探测 ④.再哈希法 4.链地址法 5.桶 6.总结 1.哈希函数的引入大家都用过字典,字典的优点是我们可以通过前面的目录快速定位到所要查找的单词.如果我们想把一本英文字典的每个单词,从 a 到 zyzzyva(这是牛津字典的最后一个单词),都写入计算机内存,以便快速读写,那么哈希表是个不错的选择. 这里我们将范围缩小点,比如想在内存中存储5000个英文单词.我们可能想到每个单词
Java数据结构之实现哈希表的分离链接法

哈希表的分离链接法原理 Hash Table可以看作是一种特殊的数组.他的原理基本上跟数组相同,给他一个数据,经过自己设置的哈希函数变换得到一个位置,并在这个位置当中放置该数据.哦对了,他还有个名字叫散列 0 1 数据1 数据2 就像这个数组,0号位置放着数据1,1号位置放数据2 而我们的哈希表则是通过一个函数f(x) 把数据1变成0,把数据2变成1,然后在得到位置插入数据1和数据2. 非常重要的是哈希表的长度为素数最好!! 而且当插入数据大于一半的时候我们要进行扩充!!! 冲突问题产生现在
java中哈希表及其应用详解

哈希表也称为散列表,是用来存储群体对象的集合类结构. 什么是哈希表数组和向量都可以存储对象,但对象的存储位置是随机的,也就是说对象本身与其存储位置之间没有必然的联系.当要查找一个对象时,只能以某种顺序(如顺序查找或二分查找)与各个元素进行比较,当数组或向量中的元素数量很多时,查找的效率会明显的降低. 一种有效的存储方式,是不与其他元素进行比较,一次存取便能得到所需要的记录.这就需要在对象的存储位置和对象的关键属性(设为 k)之间建立一个特定的对应关系(设为 f),使每个对象与一个唯一的存储位置
java数据结构和算法中哈希表知识点详解

树的结构说得差不多了,现在我们来说说一种数据结构叫做哈希表(hash table),哈希表有是干什么用的呢?我们知道树的操作的时间复杂度通常为O(logN),那有没有更快的数据结构?当然有,那就是哈希表: 1.哈希表简介哈希表(hash table)是一种数据结构,提供很快速的插入和查找操作(有的时候甚至删除操作也是),时间复杂度为O(1),对比时间复杂度就可以知道哈希表比树的效率快得多,并且哈希表的实现也相对容易,然而没有任何一种数据结构是完美的,哈希表也是:哈希表最大的缺陷就是基于数组,因
Java 哈希表详解（google 公司的上机题）

1 哈希表(散列)-Google 上机题 1) 看一个实际需求,google 公司的一个上机题: 2) 有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址..),当输入该员工的 id 时,要求查找到该员工的所有信息. 3) 要求: 不使用数据库,尽量节省内存,速度越快越好=>哈希表(散列) 2 哈希表的基本介绍散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构.也就是说,它通过把关键码值映射到表中一个位置
Java超详细分析讲解哈希表

目录哈希表概念哈希函数的构造平均数取中法折叠法保留余数法哈希冲突问题以及解决方法开放地址法再哈希函数法公共溢出区法链式地址法哈希表的填充因子代码实现哈希函数添加数据删除数据判断哈希表是否为空遍历哈希表获得哈希表已存键值对个数哈希表概念散列表,又称为哈希表(Hash table),采用散列技术将记录存储在一块连续的存储空间中. 在散列表中,我们通过某个函数f,使得存储位置 = f(关键字),这样我们可以不需要比较关键字就可获得需要的记录的存储位置. 散列技术
Java深入了解数据结构之哈希表篇

目录 1,概念 2,冲突-避免 3,冲突-避免-哈希函数设计 4,冲突-避免-负载因子调节 5,冲突-解决-闭散列 ①线性探测 ②二次探测 6,冲突-解决-开散列/哈希桶 7,完整代码 1,概念顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较.顺序查找时间复杂度为O(N),平衡树中为树的高度,即O( ),搜索的效率取决于搜索过程中元素的比较次数. 理想的搜索方法:可以不经过任何比较,一次直接从表中得到要搜索的元素. 如果构造一
Java真题实练掌握哈希表的使用

目录 1.多数元素题目描述思路详解代码与结果 2.数组中的k-diff数对题目描述思路详解代码与结果 3.缺失的第一个正数题目描述思路详解代码与结果 1.多数元素题目描述思路详解这个思路比较简单,先排序,排序过后遍历如果后一个等于前一个输出就好代码与结果 class Solution { public int majorityElement(int[] nums) { Arrays.sort(nums); return nums[nums.length / 2]; }
Java数据结构优先队列实练

目录最后一块石头的重量题目描述思路详解代码与结果装满杯子需要的最短总时长题目描述思路详解代码与结果移除石子的最大得分题目描述思路详解代码与结果最后一块石头的重量题目描述思路详解这里采用最大堆进行解题. 我们首先考虑,每次拿出两个最大的进行比较,然后大的减去小的重新放入不就完成了嘛. 首先我们创建一个优先队列,遍历重量,放入队列.依次取出重量最大的和第二大的,如果a>b就把a-b重新放入.直到队列里面的元素只剩1个的时候,输出结果. 代码与结果 class Solu
java蓝桥杯历年真题及答案整理(小结)

蓝桥杯java历年真题及答案整理(闭关一个月,呕心沥血整理出来的) 1 全排列是这样的,如果给定N个不同字符,将这N个字符全排列,最终的结果将会是N!种.如:给定 A.B.C三个不同的字符,则结果为:ABC.ACB.BAC.BCA.CAB.CBA一共3!=3*2=6种情况. package Question1_9; import java.util.Scanner; import java.util.Vector; public class Question1 { public static
Java 链表实战真题训练

目录 1.删除值为val的所有节点 2.反转链表 3.返回链表中间节点 4.返回链表第K个节点 5.合并有序链表 6.按值分割链表 7.判读回文链表 8.找两个链表的公共节点 9.判断成环链表 10.返回成环链表的入口每个题目后面有放对应题目的OJ链接,大家可以先了解一下解题思路,然后自己先去做一下. 1.删除值为val的所有节点删除链表中等于给定值val的所有节点.[OJ链接] 定义两个指针prev.cur,cur指向头节点的下一个节点,prev始终指向cur的前一个结点(方便删除节点).
Java 栈与队列实战真题训练

目录 1.实现循环队列 (1)数组下标实现循环 (2)区分队列的满与空 2.队列实现栈 3.栈实现队列 4.实现最小栈 1.实现循环队列 [OJ链接] 循环队列一般通过数组实现.我们需要解决几个问题. (1)数组下标实现循环 a.下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length.通俗一点,就是如果我们的数组大小为8,下标走到了7,再往后如何回到0,我们可以(index+1)%8来实现. b.下标最前再
Java代码实现哈希表（google 公司的上机题）

目录 1 哈希表(散列)-Google 上机题 2 哈希表的基本介绍 3. google 公司的一个上机题: 1 哈希表(散列)-Google 上机题 1) 看一个实际需求,google 公司的一个上机题: 2) 有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址..),当输入该员工的 id 时,要求查找到该员工的所有信息. 3) 要求: 不使用数据库,尽量节省内存,速度越快越好=>哈希表(散列) 2 哈希表的基本介绍散列表(Hash table,也叫哈希表)
Java数组与二维数组及替换空格实战真题讲解

目录数组中重复的数字题目描述思路详解代码与结果二维数组中的查找题目描述思路详解代码与结果替换空格题目描述思路详解代码与结果数组中重复的数字题目描述思路详解本题的思路比较简单,首先将这个数组排序,遍历数组,找到当前的和前一个相同的直接输出就好了.没找到输出-1. 注意:这个方法要注意循环的时候下标要从1开始哦,不然会报数组下标异常滴. 代码与结果 import java.util.*; public class Solution { /** * 代码中的类名.方法名
Java跳跃游戏实例真题解决思路详解

目录变式题—跳跃游戏 I 一.题目描述二.思路三.代码变式题—跳跃游戏 II 一.题目描述二.思路三.代码变式题—跳跃游戏 I 一.题目描述给定一个非负整数数组 nums ,你最初位于数组的第一个下标 .数组中的每个元素代表你在该位置可以跳跃的最大长度.判断你是否能够到达最后一个下标. 来源:https://leetcode.cn/problems/jump-game/ 示例: 二.思路本题可以使用贪心法解决,对每个能到达的位置(可覆盖到的位置),计算其每次能覆盖的最大长度,