数组中重复的数字

思路1：哈希法

1. 由于所有元素值是有范围的，因此可以用一个长度为n的数组，下标表示序列中的每一个值，下标对应的值表示该下标出现的次数。
2. 只需扫描一次原序列，就统计出所有元素出现的次数；
3. 再扫描一次哈希数组，找到一个出现次数大于1的值即可。

这种方法时间复杂度和空间复杂度都为O(n)。

public boolean duplicate(int array[],int length,int [] duplication) {
    if ( array==null ) return false;

    // 判断数组是否合法（每个数都在0~n-1之间）
    for ( int i=0; i<length; i++ ) {
        if ( array[i]<0 || array[i]>length-1 ) {
            return false;
        }
    }

    // key step
    int[] hash = new int[length];
    for( int i=0; i<length; i++ ){
        hash[array[i]]++;
    }
    for(int i=0; i<length; i++){
        if ( hash[i]>1 ) {
            duplication[0] = i;
            return true;
        }
    }
    return false;
}

思路2：高级

此大法利用了哈希的特性，但不需要额外的存储空间。 因此时间复杂度为O(n)，不需要额外空间！

1. 把当前序列当成是一个下标和下标对应值是相同的数组；
2. 遍历数组，判断当前位的值和下标是否相等： 2.1. 若相等，则遍历下一位； 2.2. 若不等，则将当前位置i上的元素和a[i]位置上的元素比较：若它们相等，则成功！若不等，则将它们两交换。换完之后a[i]位置上的值和它的下标是对应的，但i位置上的元素和下标并不一定对应；重复2.2的操作，直到当前位置i的值也为i，将i向后移一位，再重复2.

public boolean duplicate(int array[],int length,int [] duplication) {
    if ( array==null ) return false;

    // 判断数组是否合法（每个数都在0~n-1之间）
    for ( int i=0; i<length; i++ ) {
        if ( array[i]<0 || array[i]>length-1 ) {
            return false;
        }
    }

    // key step
    for( int i=0; i<length; i++ ){
        while( i!=array[i] ){
            if ( array[i] == array[array[i]] ) {
                duplication[0] = array[i];
                return true;
            }

            int temp = array[i];
            array[i] = array[array[i]];
            array[array[i]] = temp;
        }
    }

    return false;
}

// 别的我不知道，Java版本的这个题目出得跟****一样。

/*
1、判断输入数组有无元素非法
2、从头扫到尾，只要当前元素值与下标不同，就做一次判断,numbers[i]与numbers[numbers[i]]，相等就认为找到了
重复元素，返回true,否则就交换两者，继续循环。直到最后还没找到认为没找到重复元素，返回false
*/
class Solution {
public:
    // Parameters:
    //        numbers:     an array of integers
    //        length:      the length of array numbers
    //        duplication: (Output) the duplicated number in the array number
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    bool duplicate(int numbers[], int length, int* duplication) {
        if(length<=0||numbers==NULL)
            return false;
        //判断每一个元素是否非法
        for(int i=0;i<length;++i)
        {
            if(numbers[i]<=0||numbers[i]>length-1)
                return false;
        }
        for(int i=0;i<length;++i)
        {
            while(numbers[i]!=i)
            {
                if(numbers[i]==numbers[numbers[i]])
                {
                    *duplication = numbers[i];
                    return true;
                }
                //交换numbers[i]和numbers[numbers[i]]
                int temp = numbers[i];
                numbers[i] = numbers[temp];
                numbers[temp] = temp;
            }
        }
        return false;
        
    }
};

import java.util.*;
public class Solution {    
public boolean duplicate(int numbers[],int length,int [] duplication) {
//方法1：
     if(numbers == null || numbers.length == 0) return false;
        Arrays.sort(numbers);
        int flag = 0;//做标记
        for(int i=0;i<length-1;i++) {
            if(numbers[i] == numbers[i+1]) {
                duplication[0] = numbers[i];
                flag = 1;
                break;
            }
        }
        return flag == 1? true:false;
//方法2：
        HashSet<Integer> hs = new HashSet<>();
        for(int i=0;i<length;i++) {
            if(!hs.add(numbers[i])) {
                duplication[0]=numbers[i];
                return true;
            }
        }
        return false;
    }
}

public class Solution {
    public boolean duplicate(int numbers[],int length,int [] duplication) {
    	int[] assist = new int [length];
        for(int i = 0; i < length; i++){
            if(assist[numbers[i]] == 0){
                assist[numbers[i]] ++;
            }else{
                duplication[0] = numbers[i];
                return true;
            }
        }
        return false;
    }
}

//时间O(n)， 空间O(1)
public class Solution {
        public boolean duplicate(int numbers[],int length,int [] duplication) {
        if(numbers == null || length <= 0) {
            return false;
        }
        
        for(int i = 0; i < length; i++) {
            while(numbers[i] != i) {
                if(numbers[i] == numbers[numbers[i]]) {
                    duplication[0] = numbers[i];
                    return true;
                }
                int temp = numbers[i];
                numbers[i] = numbers[temp];
                numbers[temp] = temp;
            }
        }
        
        return false;
    }
} 
/* 一开始交换写错了写成了这：
int temp = numbers[i];
numbers[i] = numbers[numbers[i]];
numbers[numbers[i]] = temp;
于是就错了...

这就是剑指offer的思路。
*/

/*
 *   对BoTinker的完善
 */
class Solution {
public:
    // Parameters:
    //        numbers:     an array of integers
    //        length:      the length of array numbers
    //        duplication: (Output) the duplicated number in the array number
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    bool duplicate(int numbers[], int length, int* duplication) {      
        for(int i=0;i<length;i++){            
            int j=numbers[i]%length;
            numbers[j]+=length;
            if(numbers[j]>=(2*length)){
                *duplication = numbers[j]%length;
                return true;
            }                                  
        }
        return false;       
    }
};

class Solution {
public:
    bool duplicate(int numbers[], int length, int* duplication) {
        if(length<=1) return false;
        vector<int> numbers_index(length,0);
        for(int i=0;i<length;i++){
            numbers_index[numbers[i]]++;
            if(numbers_index[numbers[i]]>1){
                *duplication=numbers[i]; 
                return true;
            } 
        }
        return false;
    }
};

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) {
    	StringBuffer sb = new StringBuffer();	
        for(int i = 0; i < length; i++){
                sb.append(numbers[i] + "");
            }
        for(int j = 0; j < length; j++){
            if(sb.indexOf(numbers[j]+"") != sb.lastIndexOf(numbers[j]+"")){
                duplication[0] = numbers[j];
                return true;
            }
        }
        return false;
    }
}

//duplication只有一个值，居然还用指针，醉了

   bool duplicate(int numbers[], int length, int* duplication) {
        if(length<=0) return false;
        int index=0;
        map<int,int>m;
        for(int i=0;i<length;++i)
        {
             ++m[numbers[i]];
            if(m[numbers[i]]>1) {duplication[0]=numbers[i];return true;}
        }
        return false;
    }
};

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        cur = 0
        while cur < len(numbers):
            if numbers[cur] == cur:
                cur += 1
                continue
                
            if numbers[cur] == numbers[numbers[cur]]:
                duplication[0] = numbers[cur]
                return True
            
            # 注意这里不能直接multiple assignment
            temp = numbers[cur]
            numbers[cur] = numbers[numbers[cur]]
            numbers[temp] = temp
        return False

剑指Offer-数组中重复的数字

package Array;

/**
 * 数组中重复的数字
 *在一个长度为n的数组里的所有数字都在0到n-1的范围内。
 * 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
 * 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
 * 思路：
 * 数组中的数字都在0到n-1的数字范围内。如果数组中没有重复出现的数字，那么当数组排序后数字i就出现在数组中下标为i的元素处。那么数组中如果存在重复数字的话，有些位置的对应的数字就没有出现，而有些位置可能存在多个数字。数组用numbers表示
 那么我们重排这个数组。从第0个元素开始。
 1、比较numbers[i]和i的值，如果i与numbers[i]相等，也就是对数组排序后，numbers[i]就应该在对应的数组的第i个位置处，那么继续判断下一个位置。
 2、如果i和numbers[i]的值不相等，那么判断以numbers[i]为下标的数组元素是什么。
 2.1、如果numbers[numbers[i]]等于numbers[i]的话，那么就是说有两个相同的值了，重复了。找到了重复的数字
 2.2、如果numbers[numbers[i]]不等于numbers[i]的话，那么就将numbers[numbers[i]]和numbers[i]互换。继续进行1的判断。
 3、循环退出的条件是直至数组最后一个元素，仍没有找到重复的数字，数组中不存在重复的数字。
 */
public class Solution02 {
    // 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 static void main(String[] args) {
        int[] arr ={2,3,1,0,2,5,3};
        int[] duplication = {-1};
        duplicate(arr,arr.length,duplication);
        System.out.println(duplication[0]);
    }
    public static boolean duplicate(int numbers[],int length,int [] duplication) {
        if(length<=0||numbers==null){
            return false;
        }
        //判断数组数据是否合法
        for(int i=0;i<length;i++){
            if(numbers[i]<0||numbers[i]>length-1){
                return false;
            }
        }

        for(int i=0;i<length;i++){
            while(numbers[i]!=i){
                if(numbers[i]==numbers[numbers[i]]){
                    duplication[0] = numbers[i];
                    return true;
                }else{
                    //交换numbers[i]和numbers[numbers[i]]
                    int temp = numbers[i];
                    numbers[i] = numbers[temp];
                    numbers[temp] = temp;
                }
            }
        }
        return false;
    }
}

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map.Entry;
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
	boolean duplicate(int numbers[],int length,int [] duplication) {
		HashMap<Integer, Integer> countMap = new HashMap<Integer, Integer>();
		if(length < 2||numbers==null){
			return false;
		}
		int j = 1;
		for(int i = 0;i < length;i++){
			if(countMap.get(numbers[i]) == null){
				j = 1;
				countMap.put(numbers[i], j);
			}else{
				j = countMap.get(numbers[i]);
				j++;
				countMap.put(numbers[i], j);
			}
		}
		Iterator iter = countMap.entrySet().iterator();
		while(iter.hasNext()){
			Entry<Integer, Integer> entry = (Entry<Integer, Integer>) iter.next();
			Integer key = entry.getKey();
			Integer val = countMap.get(key);
			if(val > 1){
				duplication[0] = key;
				//	              System.out.println("first:"+num1[0]);
				return true;
			}
		}
		return false;
	}
}

function duplicate(numbers, duplication)
{
    // write code here
    //这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    //函数返回True/False
    let len = 0
    let arr = []
    while(len<numbers.length){
        var val = numbers[len];
        if(arr[val]!=undefined){
            duplication[0] = val
            return true
        }else{
            arr[val] = len
        }
        len++
    }
    return false
}

class Solution {
public:
    // Parameters:
    //        numbers:     an array of integers
    //        length:      the length of array numbers
    //        duplication: (Output) the duplicated number in the array number
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    bool duplicate(int numbers[], int length, int* duplication) {
        for(int i=0;i<length;i++)
        {
            if(length <= 0)
                return false;
            if(length == 1)
            {
                *duplication = numbers[0];
                return false;
            }
            if(length > 1)
            {
                set<int> s;
                for(int i =0;i<length;i++)
                    if(!s.insert(numbers[i]).second)
                    {
                        *duplication = numbers[i];
                        return true;
                    }
            }           
            return false;
        }
    }
};

import java.util.HashMap;

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 < 2 || numbers == null) {
            return false;
        }
        // 是否有重复值
        boolean isSuccess = false;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < length; i++) {
            if (!map.containsKey(numbers[i])) {
                map.put(numbers[i], 1);
            } else {
                int b = map.get(numbers[i]);
                map.put(numbers[i], b+1);
                isSuccess = true;
            }
        }
        for (int i = 0; i < length; i++) {
            if (map.get(numbers[i]) > 1){
                duplication[0] = numbers[i];
                return isSuccess;
            }
        }
        return isSuccess;
    }
}