题目: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;,然后求出给定数组中所有元素的和,两个值的差就是缺失的那个数。程序如下:
class="java" name="code">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/