头一次见这么贪心的题

元老

又要低时间复杂度, 又要低空间复杂度.一时间能想到的方案全被否决了, 有点摸不到头脑.

禁回忆

[Java] 纯文本查看 复制代码

package com.miko.admin;


public class FirstMissingPositive {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            // 判断数字
            while (nums >= 1 && nums <= n && nums[nums - 1] != nums) {
                int targetIdx = nums - 1;
                int temp = nums[targetIdx];
                nums[targetIdx] = nums;
                nums = temp;
            }
        }

        // 缺失最小正整数
        for (int i = 0; i < n; i++) {
            if (nums != i + 1) {
                return i + 1;
            }
        }
        // 全部存在，缺失 n+1
        return n + 1;
    }

    // 测试
    public static void main(String[] args) {
        FirstMissingPositive sol = new FirstMissingPositive();
        System.out.println(sol.firstMissingPositive(new int[]{3, 4, -1, 1}));  // 2
        System.out.println(sol.firstMissingPositive(new int[]{1, 2, 3}));       // 4
        System.out.println(sol.firstMissingPositive(new int[]{7, 8, 9, 11, 12}));// 1
        System.out.println(sol.firstMissingPositive(new int[]{}));            // 1
        System.out.println(sol.firstMissingPositive(new int[]{1}));          // 2
        System.out.println(sol.firstMissingPositive(new int[]{2, 1}));         // 3
    }
}

禁回忆

问题的解法就在题目当中。就四个字，原地哈希

神女软件定制

想了下，没想出算法