Java真题实练掌握哈希表的使用
作者:风铃听雨~ 发布时间:2023-11-09 06:33:15
标签:Java,哈希表
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;
}
}
来源:https://blog.csdn.net/muzi_longren/article/details/125766161
0
投稿
猜你喜欢
- 有时候,我们需要制作一个Word模板文档,然后发给用户填写,但我们希望用户只能在指定位置填写内容,其他内容不允许编辑和修改。这时候我们就可以
- 前言:mybatisplus 可以说是对mybatis更好的拓展,一些简单的增删改查的操作已经被作者实现,我们只需引用即可。1.数据库建表这
- 简要:EigenFace是基于PCA降维的人脸识别算法,PCA是使整体数据降维后的方差最大,没有考虑降维后类间的变化。 它是将图像
- 1.ArrayList 是基数组结构的,需要连续的内存空间从构造函数可以看出,ArrayList内部用一个Object数组来保存数据。对于无
- 线程状态NEW:刚创建未启动的线程RUNNABLE:正在执行状态BLOCKED:处于阻塞状态的线程WAITING:正在等待另一个线程执行特定
- 要实现摇一摇的功能,类似于微信的摇一摇方法1:通过分析加速计数据来判断是否进行了摇一摇操作(比较复杂)方法2:iOS自带的Shake监控AP
- Android 中ScrollView嵌套GridView,ListView的实例在Android开发中,经常有一些UI需要进行固定styl
- 一、判断语句最常用的顺序结构只能顺序执行,并不能进行判断和选择。于是便有了下面两种分支结构if语句switch语句1. if语句一个if语句
- 摘要:vs2019新鲜出炉,配置opencv又有哪些不一样呢,这个教程将会一步一步的教你如何配置opencv和跑动opencv一个简单的项目
- 具体代码如下所示:***web.xml***<?xml version="1.0" encoding="
- Handler是什么?Handler 是一个可以实现多线程间切换的类,通过 Handler 可以轻松地将一个任务切换到 Handler 所在
- 今天重新装了编译器,结果崩无极限,真是日了狗了了。刚刚才知道问题在哪边。好了,说正事,对于ios开发我没接触,不是很了解,百度了半天,差不多
- 近期,Apache SkyWalking 修复了一个隐藏了近4年的Bug - TTL timer 可能失效问题,这个 bug 在 SkyWa
- 前言在java Thread类中,我们会看到interrupt()、interrupted()及isInterrupted(),在大多数情况
- ActiveMQ是什么ActiveMQ是消息队列技术,为解决高并发问题而生ActiveMQ生产者消费者模型(生产者和消费者可以跨平台、跨系统
- 一:什么是SparkSQL?(一)SparkSQL简介Spark SQL是Spark的一个模块,用于处理结构化的数据,它提供了一个数据抽象D
- HashMap和HashTable,这二者的区别经常被别人问起,今天在此总结一下。(一)继承的历史不同public class
- java有两种类型的classload,一种是user-defined的,一种是jvm内置的bootstrap class loader,所
- 一 前言redis在分布式应用十分广泛,本篇文章也是互联网面试的重点内容,读者至少需要知道为什么需要分布式锁,分布式锁的实现原理,分布式锁的
- 实例如下:import java.lang.reflect.Field;import java.lang.reflect.Invocatio