一个数组面试题

墨蓝 2022-05-22 01:58 197阅读 0赞

**In an unsorted array of first N natural numbers. The array contains a number which is duplicated and one is missing. Find both the numbers. 一个含有前N个自然数的未排序数组，其中一个数出现了两次，一个没有出现，找出这两个数。**

来源：careercup 亚马逊美国面试题 [http://www.careercup.com/question?id=13729662][http_www.careercup.com_question_id_13729662]

**【解答】**

首先很容易想到naive approach，新建一个大小为N的数组作为flag，时间复杂度为O(N)，另外需要O(N)的space。

这里[CodeCracker][] 利用数学方法给出了一个很好的解答。

前N个自然数的和是(n+1) n / 2，设重复出现的数是x，没出现的数是y，则输入数组的和是(n+1)\*n +x - y；同样前N个自然数的平方和是 n\*(n+1)(2n+1)/6，输入数组的平方和是 n\*(n+1)(2n+1)/6 +x^2-y^2，于是我们可以算出 ( x -  y ) 和 ( x^2 - y^2 )，进而算出x 和 y。因为需要一次求和过程，时间复杂度为O(N)。

下面给出JAVA语言的算法实现：

package mianshiti;
    /**
     * 寻找一个数组中的重复出现的数字和没有出现的数字
     * @author majing
     *题目：一个含有N个自然数的未排序数组中，其中一个数出现两次，一个数没有出现，现在需要找出这两个数
     */
    public class SearchDupAndMiss {
    
    	/**
    	 * @param args
    	 */
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		int[] array={1,2,4,6,5,6,7};
    		search(array,array.length);
    	}
    	
    	public static void search(int[] array,int length)
    	{
    		int errorsum=0;
    		int squareerror=0;
    		for(int i=0;i<length;i++)
    		{
    			errorsum+=(array[i]-(i+1));
    			squareerror+=(array[i]*array[i]-(i+1)*(i+1));
    		}
    		squareerror/=errorsum;
    		System.out.println("重复的数为："+(squareerror+errorsum)/2);
    		System.out.println("丢失的数为："+(squareerror-errorsum)/2);
    	}
    
    }

在上面的程序中，errorsum记录原数组与正常的前N个自然数组成的数组的差值，而squareerror记录着两个数组的平方差值，根据上面阐述可以知道

x-y=errorsum

x^2 - y^2=squareerror

所以

x+y=squareerror/errorsum

重复的数为：6
    丢失的数为：3

[http_www.careercup.com_question_id_13729662]: http://www.careercup.com/question?id=13729662
[CodeCracker]: http://www.careercup.com/user?id=13716668