区块链技术博客
www.b2bchain.cn

原地置换,手动模拟哈希表

这篇文章主要介绍了原地置换,手动模拟哈希表,通过具体代码讲解7728并且分析了原地置换,手动模拟哈希表的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了原地置换,手动模拟哈希表。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/?p=7728。具体如下:

剑指 Offer 03. 数组中重复的数字

法1:HASHSET 

 class Solution {     public int findRepeatNumber(int[] nums) {          Set<Integer> set=new HashSet<>();         for(int num:nums){             if(!set.add(num)){                   return num;             }         }         return -1;     } }

 法2:原地置换(下标与当前值是否相同– 下标1 当前值1)

如果没有重复数字,那么正常排序后,数字i应该在下标为i的位置,所以思路是重头扫描数组,遇到下标为i的数字如果不是i的话,(假设为m),那么我们就拿与下标m的数字交换。在交换过程中,如果有重复的数字发生,那么终止返回

 class Solution {     public int findRepeatNumber(int[] nums) {         int temp;         for(int i=0;i<nums.length;i++){             while (nums[i]!=i){                 if(nums[i]==nums[nums[i]]){                     return nums[i];                 } //交换是必须的,不等就必然要交换。 //注意交换时候下标是t,。。。因为后面变了。                 temp=nums[i];                 nums[i]=nums[temp];                 nums[temp]=temp;             }         }         return -1;     } }  

41. 缺失的第一个正数

 class Solution {     public int firstMissingPositive(int[] nums) {         int len=nums.length;         for (int i = 0; i <len ; i++) {                   /*        只有在 nums[i] 是 [1, len] 之间的数,并且不在自己应该呆的位置, nums[i] != i + 1 ,         并且 它应该呆的位置没有被同伴占有(即存在重复值占有)	nums[nums[i] - 1] != nums[i] 的时候才进行交换          为什么使用 while ? 因为交换后,原本 i 位置的 nums[i] 已经交换到了别的地方,         交换后到这里的新值不一定是适合这个位置的,因此需要重新进行判断交换         如果使用 if,那么进行一次交换后,i 就会 +1 进入下一个循环,那么交换过来的新值就没有去找到它该有的位置          比如 nums = [3, 4, -1, 1] 当 3 进行交换后, nums 变成 [-1,4,3,1],          此时 i == 0,如果使用 if ,那么会进入下一个循环, 这个 -1 就没有进行处理         */             while(nums[i]>0 && nums[i]<=len && nums[i]!=nums[nums[i]-1]){                 int t=nums[i];                 nums[i]=nums[t-1];                 nums[t-1]=t;             }         }         for (int j = 0; j <len ; j++) {             if(nums[j]!=j+1) return j+1;         }         return len+1;     } }

442. 数组中重复的数据 

因为给定题目  值为 1—n  而下标是从0开始  所以 对应 值减一 

当前数值-1  作为下标  的 值 变为负数

int[] arr=new int[]{3,2,4,11,33};

比如3 修改对应下标为2的位置的数也就是4 变为 -4;

 class Solution {     public List<Integer> findDuplicates(int[] nums) {         List<Integer> ans=new ArrayList<>();         int len=nums.length;           for(int i=0;i<len;i++){              int num= Math.abs(nums[i])-1;              if(nums[num]<0) ans.add(num+1);              nums[num]= - nums[num];           }          return ans;      } }

448. 找到所有数组中消失的数字

 class Solution {     public List<Integer> findDisappearedNumbers(int[] nums) {             List<Integer> ans=new ArrayList<>();             int len=nums.length;             //值   1 2 3 4             //下标 0 1 2 3             for(int i=0;i<len;i++){                 int index=Math.abs(nums[i])-1;                if(nums[index]>0)  nums[index]= -nums[index];             }             for(int i=0;i<len;i++){                if(nums[i]>0) ans.add(i+1);             }       return ans;     } }

 

本文地址https://www.b2bchain.cn/?p=7728

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 原地置换,手动模拟哈希表
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们