Java真题实练掌握哈希表的使用
作者:风铃听雨~ 时间:2023-11-09 06:33:15
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
标签:Java,哈希表
0
投稿
猜你喜欢
Android控件View的文字周围添加图标
2023-02-20 04:04:44
Java Swing中的JButton、JComboBox、JList和JColorChooser组件使用案例
2023-07-11 17:32:06
Java把数字格式化为货币字符串实例代码
2022-10-13 23:17:27
Android 中启动自己另一个程序的activity如何实现
2022-05-17 05:24:56
C#实现带消息数的App图标
2022-03-08 11:30:52
Spring Cache简单介绍和使用大全
2023-11-25 04:46:46
Android 使用mediaplayer播放res/raw文件夹中的音乐的实例
2023-12-19 08:28:11
Mybatis中Collection集合标签的使用详解
2023-07-10 05:09:35
Java中SimpleDateFormat日期格式转换详解及代码示例
2023-09-04 22:13:43
Android引导页面的简单实现
2023-08-06 04:24:32
基于Java代码操作Redis过程详解
2022-03-28 06:53:58
通过自定制LogManager实现程序完全自定义的logger
2022-05-11 06:33:15
Springboot Thymeleaf模板文件调用Java类静态方法
2023-11-25 05:34:47
Java的运算符和程序逻辑控制你了解吗
2023-01-19 10:01:59
C#写入XML文档
2022-03-21 18:08:33
Android图片翻转动画简易实现代码
2023-03-12 02:33:35
Kotlin协程Dispatchers原理示例详解
2022-09-26 00:09:45
Spring Boot整合JWT的实现步骤
2022-07-17 04:48:58
Flutter实现心动的动画特效
2021-09-03 18:08:01
Android 捕获运行时异常详解
2023-12-22 21:16:30