数据结构与算法

数组--缺失的第一个整数

2020-01-06  本文已影响0人  暮想sun

给定一个未排序的整数数组,找出其中没有出现的最小的正整数。
例:输入: [7,8,9,11,12] 输出: 1
思路:排序,根据排序好的数组,假设最小未出现的正整数为min(初始化为1),依次比较再替换min

    public static int firstMissingPositive(int[] nums) {
        //排序
        Arrays.sort(nums);
        int left = 0;
        int min = 1;
        //循环数组元素
        while (left < nums.length) {

            //数据小于min,向右移动
            if (nums[left] < min) {
                left++;
            } else if (nums[left] == min) {
                left++;
                min = min + 1;
                //出现大于min的数据,说明min为最小
            } else if (nums[left] > min) {
                break;
            }
        }

        return min;

    }
上一篇 下一篇

猜你喜欢

热点阅读