找出1到n缺失的一个数_JAVA_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > JAVA > 找出1到n缺失的一个数

找出1到n缺失的一个数

 2014/11/18 16:10:15  MouseLearnJava  程序员俱乐部  我要评论(0)
  • 摘要:题目:Problemdescription:YouhaveanarrayAofsizen–1containingnumbersfrom1tonsothereisonemissingnumber,findit!本文给出解决上述问题的两个方法。方法一:求和然后相减在这个方法中,首先求出1到n的和,可以使用数学公式inttotal=(n*(n+1))/2;,然后求出给定数组中所有元素的和,两个值的差就是缺失的那个数。程序如下:publicclassFindMissingNumber
  • 标签:一个

题目: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/

发表评论
用户名: 匿名