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

ゞ浴缸里的玫瑰 2022-05-29 10:36 156阅读 0赞

![Center][]

import java.util.*;
    //数组中未出现的最小正整数
    public class MinInt{
    	  
          //方法一、排序法
    	  public static int GetminInt(int[]arr)
    	  {
    	  	if(arr==null)
    	  	{
    	  		 return -1;
    	  	}
    	  	Arrays.sort(arr);
    	  	if(arr[arr.length-1]<=0)
    	  	{
    	  		  return 1;
    	  	}
    	  	int res=arr.length-1;
    	  	int re=1;
    	    while(arr[res]>0)
            {
                --res;
    	  	}
    	  	int k=0;
    	  	for(int i=res+1;i<arr.length;i++)
    	  	{   
    	  		 k=i-res;
                if(arr[i]!=k)
                {
                	re=k;
                	break;
                }
    	  	   
    	  	}
    	  	//遍历完最后一个数
    	  	if(k==arr.length-res-1)
    	  	{
    	  		re=arr.length-res;
    	  	}
            return re;
    	  }
    	  //方法二
    	  public static int GetminInt02(int[]arr)
    	  {
    	  	 if(arr==null)
    	  	 {
    	  	 	 return -1;
    	  	 }
    	  	 int l=0;
    	  	 int r=arr.length;
    	  	 while(l<r)
    	  	 {
    	  	 	 if(arr[l]==l+1)
    	  	 	 {
    	  	 	 	 l++;
    	  	 	 }else if(arr[l]<=1||arr[l]>r||(arr[arr[l]-1]==arr[l])){
                     arr[l]=arr[--r];
    	  	 	 }else{
    	  	 	 	 swap(arr,l,arr[l]-1);
    	  	 	 }
    
    	  	 }
    	  	 return l+1;
    
    	  }
    
    	   public static void swap(int[]arr,int i,int j)
    	   {
    	   	  int temp=arr[i];
    	   	  arr[i]=arr[j];
    	   	  arr[j]=temp;
    
    	   }
    
    	  //产生随机的数组
    	  public static int []GenerateArr(int size)
    	  {
              Random ran=new Random();
              int[]arr=new int[size];
              for(int i=0;i<size;i++)
              {
              	 int n=ran.nextInt(10);
              	 if(n%2==0)
              	 {
              	 	arr[i]=n;
              	 }else{
              	 	arr[i]=-n;
              	 }
              	     	 
              }
              return arr;
    	  }
    
    	  //遍历数组
    	  public static void PrintArr(int[]arr)
    	  {
    	  	 for(int i=0;i<arr.length;i++)
    	  	 {
    	  	 	 System.out.print(arr[i]+" ");
    	  	 }
    	  	 System.out.println();
    	  }
    	  public static void main(String[]args)
    	  {
    	  	 //System.out.println("Hello");
    	  	  PrintArr(GenerateArr(6));
    	  	  int []arr2={-1,-3,-5,0,1,2,3};
    	  	  System.out.println(GetminInt(GenerateArr(6)));
    	  	  PrintArr(arr2);
    	  	  System.out.println(GetminInt(arr2));
    	  	  System.out.println(GetminInt02(arr2));
    
    	  }
    }

![Center 1][]

[Center]: /images/20220529/02fe55c38cc34fadb73e161c81dacfe5.png
[Center 1]: /images/20220529/32f4677dc5064fe2808640e9e7a0bdd2.png