数组中未出现的最小正整数

[编程题]数组中未出现的最小正整数

热度指数：1999 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

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

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

[要求]

时间复杂度为

，空间复杂度为

输入描述:

第一行为一个整数N。表示数组长度。
接下来一行N个整数表示数组内的数

输出描述:

输出一个整数表示答案

示例1

输入

4
-1 2 3 4

输出

示例2

输入

4
1 2 3 4

输出

备注:

算法知识视频讲解

Java

绚都

自己想到的一个方法

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n=Integer.parseInt(sc.nextLine().trim());
            int[] arr=new int[n];
            String[] s = sc.nextLine().trim().split(" ");
            for (int i = 0; i < n; i++) {
                arr[i]=Integer.parseInt(s[i]);
            }
            int res=new Solution().NotOccurred(arr);
            System.out.println(res);
        }
    }
}

class Solution {
    public int NotOccurred(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            if(arr[i]>0) swap(arr,arr[i]-1,i);
        }
        for (int i = 0; i < arr.length; i++) {
            if(arr[i]!=i+1) return i+1;
        }
        return arr.length+1;
    }

    public void swap(int[] arr,int i,int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
}

发表于 2022-05-06 16:57:00 回复(0)