题目：在一个长度为n的数组里的所有数字都在0到n-1的范围内，找出数组中任意一个重复的数字。
 
测试代码：
 
 public static void main(String[] args) {
        int [] numbers  ={0,1,2,2,3,4,5};
        int [] duplication = new int[10];
        int duplicate = duplicate(numbers, duplication);
        System.out.println("duplicate is = "+duplicate);

    }
    
    public static int  duplicate(int  [] numbers,int [] duplication) {
        if(numbers.length == 0){
            return -1;
        }
        for(int i=0; i<numbers.length; i++){
            if(numbers[i]<0 || numbers[i]>=numbers.length){
                return -1;
            }
        }

        for(int j=0; j<numbers.length; j++){
            while(numbers[j] != j){
                if(numbers[j]==numbers[numbers[j]]){
                    duplication[0] = numbers[j];
                    return duplication[0];
                }
                int temp = numbers[j];
                numbers[j]=numbers[temp];
                numbers[temp]=temp;
            }
        }
        return -1;
    }
 
 

题目：在一个长度为n的数组里的所有数字都在0到n-1的范围内，找出数组中任意一个重复的数字。
 
解答：
 
public static void main(String[] args) {
        int [] numbers  ={0,1,2,2,3,4,5};
        int [] duplication = new int[10];
        int duplicate = duplicate(numbers, duplication);
        System.out.println("duplicate is = "+duplicate);

    }
    public static int  duplicate(int  [] numbers,int [] duplication) {
        if(numbers.length == 0){
            return -1;
        }
        for(int i=0; i<numbers.length; i++){
            if(numbers[i]<0 || numbers[i]>=numbers.length){
                return -1;
            }
        }

        for(int j=0; j<numbers.length; j++){
            while(numbers[j] != j){
                if(numbers[j]==numbers[numbers[j]]){
                    duplication[0] = numbers[j];
                    return duplication[0];
                }
                int temp = numbers[j];
                numbers[j]=numbers[temp];
                numbers[temp]=temp;
            }
        }
        return -1;
    }
 
 

题目：
 
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
 
思路：
 
 
代码：
 
代码中给了三个参数，值得注意的是第三个参数是储存重复数字的数组，大小为1
 
public class Solution {
    // Parameters:
    //    numbers:     an array of integers
    //    length:      the length of array numbers
    //    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
    //                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
    //    这里要特别注意~返回任意重复的一个，赋值duplication[0]
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        //首先判断不行的条件
        if(length<=0)
        {
            return false;
        }
        //创建一个boolean数组作为标志位，boolean数组占用的内容不高，默认全为false
        boolean [] arr=new boolean[length];
        //进行循环遍历
        for(int i=0;i<length;i++)
        {
            if(arr[numbers[i]]==true)
            {
                duplication[0]=numbers[i];
                return true;
            }
            arr[numbers[i]]=true;
        }
        return false;
    }
}
 
 

在美团的电话面试一面中被问到这样的问题，当时最先想到的是用全排列，然后挑出最大的一个，虽然问题可以解决，但是太暴力而且时间复杂度太大。后来想到可以通过快排直接排好序，输出就是最大值。时间复杂度也可以接受。
 
用快排实现的最大的难点就是怎么进行比较规则的设计。将给的整形转化为字符串string类型比较大小，规则设计如下：当str1 是str2 的从头开始的一部分，则str1>str2例如‘91’ 大于‘919’；否则调用string.compareTo()方法比较大小。具体代码如下：
 
代码中regionMatches()函数作用：
 
将此对象的子字符串与参数的子字符串进行比较。如果这两个子字符串表示相同的字符序列，则结果为true，当且仅当 ignoreCase 为 true 时忽略大小写。要比较的此String对象的子字符串从索引toffset处开始，
长度为len。要比较的 other的子字符串从索引ooffset处开始，长度为len。当且仅当下列至少一项为 true 时，结果才为 false，也可以自己写，只是犯懒了，就查了一下API。
 
 
 
package quickSort;

public class QuickSort {

	public static int getMid(int array[], int low, int high) {
		int temp = array[low];
		while (low < high) {
			while (low < high && bigger(temp,array[high])) {
				high--;
			}
			array[low] = array[high];

			while (low < high && bigger(array[low],temp)) {
				low++;
			}
			array[high] = array[low];
		}
		array[low] = temp;
		return low;
	}


	public static void quickSort(int[] array, int low, int high) {
		if (low < high) {
			int mid = getMid(array, low, high);
			quickSort(array, low, mid - 1);
			quickSort(array, mid + 1, high);
		}
	}
	
	public static boolean bigger(int a, int b){
		String str1 = String.valueOf(a);
		String str2 = String.valueOf(b);	
		if(str1.regionMatches(0,str2,0,str1.length()) == true 
				&& str1.length() <= str2.length()){

			//当类似9 和99比较时返回true,即'9'>"99"
			return true;	
		}
		char [] arr1 = str1.toCharArray();
		int len1 = arr1.length;
		
		char [] arr2 = str2.toCharArray();
		int len2 = arr2.length;
		
		if(str1.compareTo(str2) > 0){//字符串比较
			return true;
		}
		return false;
	}


	public static void main(String[] args) {
		int a[] = new int[] { 9,99,909,9901,8 };
		quickSort(a, 0, a.length - 1);
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] +"  ");
		}
	}
	//结果9  99  9901  909  8 
}

 在百度上也搜到另外一种方法，感觉不好理解，给大家粘出来参考一下。http://zhidao.baidu.com/link?url=77WvVjzCFPeV-UGgHZAbJJ5grsSVcvjjZX3mtE_9EEYl5pyIXnM9zGalsd5k19DFs6vBgybGyGvPLYRUOlcrNw8X1O67QvXVzvDmsHnX_ha