博客

33.数组中未出现的最小正数

题目描述

给定一个无序数组arr，找到数组中未出现的最小正整数

例如arr = [-1, 2, 3, 4]。返回1

arr = [1, 2, 3, 4]。返回5

[要求]

时间复杂度为O(n)O(n)，空间复杂度为O(1)O(1)

输入

[-1,2,3,4]

返回值

1

分析

1.最小正数是1，所以从1开始比较

2.如果相等就给1+1；一直循环

3.直到数组中没有该数字时，跳出循环

代码实现

    import java.util.*;
    
    
    public class Solution {
        /**
         * return the min number
         * @param arr int整型一维数组 the array
         * @return int整型
         */
        public int minNumberdisappered (int[] arr) {
    	        int res = 1;
    	        Arrays.sort(arr);
    	        while(true) {
    	        	for(int i=0;i<arr.length;i++) {
    	        		if(arr[i]!=res) {
    	        			return res;
    	        		}
    	        		else
    	        			res = res+1;
    	        	}
    	        }
    	    }
    }