Leetcode算法Java全解答--41. 缺失的第一个正数

港控/mmm° 2022-04-12 14:12 97阅读 0赞

# Leetcode算法Java全解答–41. 缺失的第一个正数 #

### 文章目录 ###

*  Leetcode算法Java全解答--41. 缺失的第一个正数
 *   *  题目
     *  想法
     *  结果
     *  总结
     *  代码
     *   *  我的答案
         *  大佬们的答案
         *  测试用例
     *  其他

## 题目 ##

给定一个未排序的整数数组，找出其中没有出现的最小的正整数。

说明:  
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。

示例

示例 1:
    
    输入: [1,2,0]
    输出: 3
    示例 2:
    
    输入: [3,4,-1,1]
    输出: 2
    示例 3:
    
    输入: [7,8,9,11,12]
    输出: 1

## 想法 ##

1.  错了！使用二进制来存储，将第N位的数据改成1，原来想的有二十亿数据，后面发现int只有32位，只能保证32个，错了
2.  交换法

将1放到数组 索引0位置，将2放到数组 索引1的位置，将3放到数组索引1的位置

假设交换的数据还是大于0且小于i+1，则放在合适的位置,且数据不相等，避免死循环

用的是 if判断 加上 i–,别人的方法使用while循环

然后去循环数组，数据不对就返回

## 结果 ##

超过97%的测试案例

时间复杂度/空间复杂度：O(n)/1

## 总结 ##

// TODO

## 代码 ##

### 我的答案 ###

public int firstMissingPositive(int[] nums) {
    
        if (nums.length == 0) {
            return 1;
        }
    
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                // 假设交换的数据还是大于0且<i+1，则放在合适的位置,且数据不相等，避免死循环
                if (nums[i] < nums.length + 1 && nums[i] != nums[nums[i] - 1]) {
                    int tmp = nums[nums[i] - 1];
                    nums[nums[i] - 1] = nums[i];
                    nums[i] = tmp;
                    i--;
                }
            }
        }
    
        // 然后去循环数组，数据不对就返回
        for (int i = 0; i < nums.length; i++) {
            if (i + 1 != nums[i]) {
                return i + 1;
            }
        }
        return nums.length + 1;
    }
    
    
    /**
         * 位运算，错误答案
         * @param nums
         * @return
         */
        public int bit(int[] nums) {
            long bitNum = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] > 0) {
                    // 将bitNum的第nums[i]变为1
                    // 第 i 位与0 或，值不变。第 i 位与1 或，变成1。因此，我们的目标是 num 与 一个第 i 位值为1，其它位的值都为0的数相 或
                    bitNum = bitNum | (1 << nums[i]);
                }
            }
    
            for (int i = 1; i < nums.length + 1; i++) {
                boolean zeroBit = (bitNum & (1 << i)) == 0;
                if (zeroBit) {
                    return i;
                }
            }
    
            return nums.length + 1;
        }

### 大佬们的答案 ###

/**************************************
     * 比我好的答案 better
     * ***********************************/
    public int better(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
    
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }

### 测试用例 ###

@Test
    public void test041() {
        // 创建测试案例
        int[] test1 = new int[] { 0, 1, 2 };
        int[] test2 = new int[] { 10, 4, 16, 54, 17, -7, 21, 15, 25, 31, 61, 1, 6, 12, 21, 46, 16, 56, 54, 12, 23, 20,
                38, 63, 2, 27, 35, 11, 13, 47, 13, 11, 61, 39, 0, 14, 42, 8, 16, 54, 50, 12, -10, 43, 11, -1, 24, 38,
                -10, 13, 60, 0, 44, 11, 50, 33, 48, 20, 31, -4, 2, 54, -6, 51, 6 };
        int[] test3 = new int[] { 0, 1, 2, 3, 5 };
        int[] test4 = new int[] { 2 };
    
        // 测试案例期望值
        int expResult1 = 3;
        int expResult2 = 3;
        int expResult3 = 4;
        int expResult4 = 1;
    
        Solution041 solution041 = new Solution041();
    
        int result1 = solution041.firstMissingPositive(test1);
        int result2 = solution041.firstMissingPositive(test2);
        int result3 = solution041.firstMissingPositive(test3);
        int result4 = solution041.firstMissingPositive(test4);
    
        Assert.assertEquals(expResult1, result1);
        Assert.assertEquals(expResult2, result2);
        Assert.assertEquals(expResult3, result3);
        Assert.assertEquals(expResult4, result4);
    }

## 其他 ##

代码托管码云地址：[https://gitee.com/lizhaoandroid/LeetCodeAll.git][https_gitee.com_lizhaoandroid_LeetCodeAll.git]

查看其他内容可以点击专栏或者我的博客哈：[https://blog.csdn.net/cmqwan][https_blog.csdn.net_cmqwan]

“大佬们的答案” 标签来自leetcode，侵权请联系我进行删改

如有疑问请联系，联系方式：QQ3060507060

[https_gitee.com_lizhaoandroid_LeetCodeAll.git]: https://gitee.com/lizhaoandroid/LeetCodeAll.git
[https_blog.csdn.net_cmqwan]: https://blog.csdn.net/cmqwan