本文共 5146 字，大约阅读时间需要 17 分钟。

原地哈希算法

原地哈希算法用来求解空间复杂度为O(1)的题目，且求解的结果范围是[0, len(nums)]之间的，nums是题目提供的求解数组。

原地哈希算法主要应用在结果范围为 [0, len(nums)] 的数组解法中，空间复杂度有限，只有一个原数组，将数组元素本身作为nums 的下标，即 nums[nums[i]]，元素本身存放到原数组下标中，数组本身值则存放标记，通过负数标记求解。下面将结合leetcode 题目做一些总结。

题目描述:

给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。 示例 1: 输入: [1,2,0]输出: 3示例 2: 输入: [3,4,-1,1]输出: 2示例 3: 输入: [7,8,9,11,12]输出: 1提示： 你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。 Related Topics 数组

题目分析：

首先想到的是利用哈希表来存储数组中的元素，然后从1开始遍历整数，不在哈希表中的第一个数字便是我们的解。我们知道了要从 1 开始遍历，那遍历到什么值为止呢？

设数组的长度为 n，如果数组中的元素正好为 [1, …, n] ，则缺失的元素为 n+1；如果数组中有非 [1, …, n] 的数字呢？则它们占用的位置就是 [1, …, n] 中缺失的那些数字的位置。所以我们要找的数字一定是在 [1, …, n+1] 之间。所以我们需要遍历的最大值为 n+1。

题目要求使用常数级别的额外空间，而我们使用哈希表来存储数字，空间复杂度为 O(n)，不满足要求。基于此，我们尝试将原数组改造成哈希表(需要修改原数组，所以题目不能要求说不能修改原数组)，这样不使用额外的空间。

我们对数组进行遍历，对于遍历到的值 num，如果它的值在 [1, n] 之间，那么就将数组中索引为 num-1 的数字打上标记，在遍历结束后，如果所有位置都被打上了标记，则答案为 n+1，否则为最小的没有打上标记的位置加 1。

由于我们只在意 [1, n] 中的数字，所以可以将其他数字做统一修改，比如改为 n+1，这样数组中的数字都为正整数，也方便了我们使用数组中的元素作为索引来用。

/** * Title：leetcode-41. 缺失的第一个正数 * * 给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。 * 示例 1: * 输入: [1,2,0] * 输出: 3 * * Description：时间复杂度为O(n)，空间复杂度为O(1) *              不能排序，不能额外的数据结构 * @author WZQ * @version 1.0.0 * @date 2021/2/4 */public class Main41 {
       /**     * 原地hash算法，数组0-n-1，结果必须是1-n+1之间，结果是索引+1     * @param nums     * @return     */    public static int firstMissingPositive(int[] nums) {
           if (nums == null || nums.length == 0){
               return 1;        }        int n = nums.length;        // 负数过滤, n + 1不在范围        for (int i = 0; i < n; i++) {
               if (nums[i] <= 0){
                   nums[i] = n + 1;            }        }        // 正整数下标i, 标记nums[nums[i]] < 0        for (int i = 0; i < n; i++) {
               // 通过绝对值保证获取到元素本身            int num = Math.abs(nums[i]);            if (num <= n && nums[num - 1] > 0){
                   nums[num - 1] *= -1;            }        }        // 负数表示该下标被访问过        for (int i = 0; i < n; i++) {
               // 未标记过的最小            if (nums[i] > 0){
                   return i+1;            }        }        return n+1;    }    public static void main(String[] args) {
           int[] arr = {
   3, 4, -1, 1};        System.out.println(firstMissingPositive(arr));    }}

其它利用原地哈希实现的题目：

import java.util.Arrays;import java.util.HashSet;import java.util.Set;/** * Title：645. 错误的集合 * Description： 原地hash算法，优化空间复杂度O(1) * * 集合 S 包含从1到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个元素复制了成了 * 集合里面的另外一个元素的值，导致集合丢失了一个整数并且有一个元素重复。  * 给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数 * 再找到丢失的整数，将它们以数组的形式返回。  * * 示例 1:  * 输入: nums = [1,2,2,4] * 输出: [2,3] * * 长度为n的数组nums包含的数字为 [1, n]，那显然原地哈希算法可以派上用场。 * 我们对数组进行遍历，对于遍历到的值num，就将数组中索引为 num-1 的数字打上标记， * 如果遍历中发现某个数字已经被打上了标记，则表示这个数字为重复数字。 * 遍历完成后，除了丢失的数字对应的位置上的元素没有标记，其余数字都被打上了标记。 * * @author WZQ * @version 1.0.0 * @date 2021/2/4 */public class Main645 {
   //    public int[] findErrorNums(int[] nums) {
   //        int[] result = new int[2];//        if (nums == null || nums.length <= 1){
   //            return result;//        }////        int length = nums.length;////        //空间复杂度n，利用数组统计个数也可以实现//        Set
   
     set = new HashSet<>();//        for (int i = 0; i < length; i++) {
   //            if (!set.contains(nums[i])){
   //                set.add(nums[i]);//            }else {
   //                result[0] = nums[i];//            }//        }////        for (int i = 1; i <= length; i++) {
   //            if (!set.contains(i)){
   //                result[1] = i;//                break;//            }//        }////        return result;//    }    /**     * 优化     * 空间复杂度O(1)     * @param nums     * @return     */    public int[] findErrorNums(int[] nums) {
           int[] result = new int[2];        if (nums == null || nums.length <= 1) {
               return result;        }        int n = nums.length;        //原地hash算法，空间复杂度O(1)        //标记        //结果是1-n，对应下标0-n-1        //如果nums[i]存在，标记nums[nums[i]-1]为负数        //nums[i]存放到下标中        for (int i = 0; i < n; i++) {
               //通过绝对值拿到原数组对象            //保证遍历后修改了数组的值，可以拿到原来的            int num = Math.abs(nums[i]);            if (nums[num - 1] > 0){
                   nums[num - 1] *= -1;            }else {
                   result[0] = num;            }        }        //统计，为正数，也就是未标记的就是缺失        for (int i = 0; i < n; i++) {
               if (nums[i] > 0){
                   result[1] = i+1;            }        }        return result;    }}
   

/** * Title：287. 寻找重复数 * Description： * * 给定一个包含 n + 1 个整数的数组 nums ， * 其数字都在 1 到 n 之间（包括 1 和 n）， * 可知至少存在一个重复的整数。 * 假设nums只有一个重复的整数 ，找出 这个重复的数。 * * @author WZQ * @version 1.0.0 * @date 2021/2/4 */public class Main287 {
       /**     * 原地哈希，时间复杂度On，空间复杂度O1     * @param nums     * @return     */    public static int findDuplicate(int[] nums) {
           //最简单就是暴力, 时间复杂度O(n*n)        //或者利用数组统计个数，空间复杂度On        //原地哈希        int n = nums.length;        //原数组标记        for (int i = 0; i < n; i++) {
               //利用负数，绝对值保证操作其他位置的数据，可以拿到原本的元素            int num = Math.abs(nums[i]);            //负数标记            if (nums[num - 1] > 0) {
                   nums[num - 1] *= -1;            } else {
                   return num;            }        }        return 0;    }}

转载地址：http://hviwi.baihongyu.com/