题目一

给定一个长度为N的整型数组arr，其中有N个互不相等的自然数1~N

请实现arr的排序

但是不要把下标0~N-1位置上的数值通过直接赋值的方式替换成1~N。

要求：时间复杂度为O(N)，额外空间复杂度为O(1)。

思路：从左向右检查，检查到需要换的以后，就直接把它放到该去的位置，然后被换掉的数，位置肯定也不对，继续重复相同的方法，最后肯定会跳回来（原因懒得说了自己想想），然后继续往下检查即可。

  

   

    

     

    
    

     

      public static void sort1(int[] arr) {
     
    
   

    

     

    
    

     
		int tmp = 0;
     
    
   

    

     

    
    

     
		int next = 0;
     
    
   

    

     

    
    

     
		for (int i = 0; i != arr.length; i++) {
     
    
   

    

     

    
    

     

      			tmp = arr[i];
     
    
   

    

     

    
    

     
			while (arr[i] != i + 1) {
     
    
   

    

     

    
    

     

       next = arr[tmp - 1];
     
    
   

    

     

    
    

     

       arr[tmp - 1] = tmp;
     
    
   

    

     

    
    

     

       tmp = next;
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
  
 

题目二

本题一般思路：依次查找找到比前后都小的数；或者选出最小数，他肯定是局部最小的；等等

但这些都是O(n)的方法，而用二分可以做到O(logn).

二分思路：

  考虑最左和最右的元素：如果arr[0]<arr[1]  return 0; arr[N-1]<arr[N-2] return N-1;

   考虑最中间元素，如果中间元素大于它左边的元素，那么局部最小值就应该在数组的左半部分

   如果中间元素小于大于它右边的元素，那么局部最小值就应该在数组的右半部分

   中间元素既小于它左边的值又小于它右边的值，那么它就是局部最小
 

题目三

给定一个整数数组arr，返回不包含本位置的累乘数组。

比如2 3 1 4返回12 8 24 6

方法一：算出所有数的乘积，每个位置除以自己即可。要注意坑：如果数组中有一个0，那么0这个位置就是其他数的乘积，其他位置全为0；如果有多个0，那么所有位置都是0.

  

   

    

     

    
    

     
	public int[] product1(int[] arr) {
     
    
   

    

     

    
    

     
		if(arr==null || arr.length<2) {
     
    
   

    

     

    
    

     
			return null;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		int count=0;//0的个数
     
    
   

    

     

    
    

     
		int all=1;//除0以外的数的乘积
     
    
   

    

     

    
    

     
		for(int i=0;i!=arr.length;i++) {
     
    
   

    

     

    
    

     
			if(arr[i]!=0) {
     
    
   

    

     

    
    

     

       all*=arr[i];
     
    
   

    

     

    
    

     

      			}else {
     
    
   

    

     

    
    

     

       count++;
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		int[] res=new int[arr.length];
     
    
   

    

     

    
    

     
		if(count==0) {
     
    
   

    

     

    
    

     
			for(int i=0;i!=arr.length;i++) {
     
    
   

    

     

    
    

     

       res[i]=all/res[i];
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      		}else if(count==1) {
     
    
   

    

     

    
    

     
			for(int i=0;i!=arr.length;i++) {
     
    
   

    

     

    
    

     
 if(arr[i]==0) {
     
    
   

    

     

    
    

     

       res[i]=all;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		return res;
     
    
   

    

     

    
    

     

      	}
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/90741340