找出1到n缺失的一个数

题目：Problem description:  You have an array A of size n – 1 containing numbers from 1 to n so there is one missing number, find it!

 

本文给出解决上述问题的两个方法。

方法一：求和然后相减

在这个方法中，首先求出1到n的和，可以使用数学公式int total = (n * (n + 1)) / 2;，然后求出给定数组中所有元素的和，两个值的差就是缺失的那个数。程序如下：

public class FindMissingNumber {
 
    public int findMethod1(int[] array, int n) {
        int total = (n * (n + 1)) / 2;
        int sum = 0;
        for (int i = 0, len = array.length; i < len; i++){
            sum += array[i];
        }
 
        return total - sum;
    }
}

 

方法二：使用异或实现

在该方法中，先要知道异或的特性：

	 A B | A XOR B
	 0 0 | 0
	 0 1 | 1
	 1 0 | 1
	 1 1 | 0

根据该特性，将会有如下的结果：

A ^ 0 = A
A ^ A = 0
A ^ B = C
C ^ A = B

所以，可以先将1到n做异或操作，得到的值再与给定数组中的所有元素进行异或操作，最后得到的那个数字就是缺失的那个数字。

基于这个思想，程序如下：

/**
 * A B | A XOR B
 * 0 0 | 0
 * 0 1 | 1
 * 1 0 | 1
 * 1 1 | 0
 * 
 * @param array
 * @param n
 * @return
 */
public int findMethod2(int[] array, int n) {
    int result = 0;
    for(int i = 1; i <= n; i++){
        result ^= i;
    }
         
    for(int i = 0, len = array.length; i < len;  i++){
        result ^= array[i];
    }
     
    return result;
}

 

测试程序和结果如下

public class FindMissingNumberTest {
    public static void main(String[] args) {
        FindMissingNumber finder = new FindMissingNumber();
        int[] array = {1,2,3,4,6,7,8};//missing 5
        System.out.println(finder.findMethod1(array, 8));//5
        System.out.println(finder.findMethod2(array, 8));//5
    }
 
}

 

原文地址 http://thecodesample.com/?p=930

更多代码 http://thecodesample.com/