Java实现升序排列的整形数组A,元素两两不相等找出A[i]=i的数据-小白筆記-匯編語言學習筆記

Java实现升序排列的整形数组A,元素两两不相等找出A[i]=i的数据

2023-09-05 阅读 320 评论 0

摘要：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 importjava.util.ArrayList; //升序排列的整形数组A,元素两两不相等。请设

  import java.util.ArrayList; 
//升序排列的整形数组A,元素两两不相等。请设计高效的算法找出A[i]=i的数据。
//使用二种方法
 public class BinarySearch { 
      
     public static void main(String[] args) { 
         int[] nums={-1,1,2,3}; 
         ArrayList<Integer> res=find(nums); 
         for(int e:res){ 
                 System.out.println(e+" "); 
         } 
          
         ArrayList<Integer> res2=binarysearch(nums); 
         for(int e:res2){ 
                 System.out.println(e+" "); 
         } 
     } 
      
     //方法一 
     public static ArrayList<Integer> find(int[] nums){ 
         int n=nums.length; 
         ArrayList<Integer> all=new ArrayList<Integer>(); 
         for(int i=0;i<n;i++){ 
             if(nums[i]==i){ 
                 all.add(nums[i]); 
             }else if(nums[i]>i){ 
                 break; 
             } 
         } 
         return all; 
     } 
      
     //方法二 
     public static ArrayList<Integer> binarysearch(int[] nums){ 
         ArrayList<Integer> all=new ArrayList<Integer>(); 
         int n=nums.length; 
         if(n==0 || nums[0]>0 || nums[n-1]<n-1){ 
             return all; 
         } 
         //至少有一个元素的值等于其下标 
         int pivot=binaryFind(nums,0,n-1); 
         all.add(pivot); 
         //向左查找所有目标元素 
         for(int i=pivot-1;i>=0 && i==nums[i];--i){ 
             all.add(i); 
         } 
         //向右查找所有的目标元素 
         for(int i=pivot+1;i<n && i==nums[i];i++){ 
             all.add(i); 
         } 
         return all; 
     } 
      
     public static int binaryFind(int[] nums,int i,int j){ //二分搜索方法 
         int mid=(i+j)/2; 
         if(nums[mid]==mid){ 
             return mid; 
         }else if(nums[mid]>mid){ 
             return binaryFind(nums,i,mid-1); 
         }else{ 
             return binaryFind(nums,mid+1,j); 
         } 
     } 
}
 

     本文转自爱情89757 51CTO博客，原文链接：http://blog.51cto.com/59465168/1965755，如需转载请自行联系原作者 

原文链接：https://hbdhgg.com/1/227.html