原地哈希
🟧概述
🔻含义： 数组当作哈希表 通过不同场景(重复整数、缺少整数)选择标记方式(交换或者标记为负数) 判断某个值/几个值 存不存在
🔻试用场景： 数组的所有数字都是从0开始或者1开始(正数) 并且对空间复杂度要求为O(1)
🔻时间复杂度： O(n)
🔻空间复杂度： O(n)
🔻注意事项：
🔸数字必须为正数
🔸不能破坏单调性
🟧模板
📌通用模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Temple{
public int Solution(int[] nums) {
int len = nums.length;
for(int i=0;i<len;++i){
int n =Math.abs(nums[i]);
int idx = n-1;
int res = markHandle(nums,idx);
return res;
}
return -1;
}
int MarkHandle(int[]nums,int idx){
if(nums[idx]<0){
return idx+1;
}else{
nums[idx]*=-1;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Temple{
public int Solution(int[] nums) {
int len = nums.length;
for(int i=0;i<len;++i){
int nextIdx = nums[i]-1;
MarkHandle(nums,nextIdx,i);
}
for(int i=0;i<len;++i){
if(i+1!=nums[i]) return i+1;
}
}
void MarkHandle(int[]nums,int l,int r){
int t = nums[l];
nums[l] = nums[r];
nums[r] = t;
}
}
🟧总结
🔻思考1:为什么使用原地哈希?
🔸因为可以原地操作数组 修改值 判断值 空间复杂度为O(1)
🔻思考2:原地哈希本质?
🔸本质就是利用数组的下标从0开始这一特性 使用数组下标当作索引