算法面试：数组编码面试问题

<b>import</b> java.util.Arrays;
<b>import</b> java.util.BitSet;
 <font><i>/** 
* Java program to find missing elements in a Integer array containing 
  * numbers from 1 to 100. 
* 
* @author Javin Paul 
*/</i></font><font>
<b>public</b> <b>class</b> MissingNumberInArray {
 
     <b>public</b> <b>static</b> <b>void</b> main(String args[]) {

        </font><font><i>// one missing number</i></font><font>
        pr<b>int</b>MissingNumber(<b>new</b> <b>int</b>[]{1, 2, 3, 4, 6}, 6);
 
        </font><font><i>// two missing number</i></font><font>
        pr<b>int</b>MissingNumber(<b>new</b> <b>int</b>[]{1, 2, 3, 4, 6, 7, 9, 8, 10}, 10);
 
        </font><font><i>// three missing number</i></font><font>
        pr<b>int</b>MissingNumber(<b>new</b> <b>int</b>[]{1, 2, 3, 4, 6, 9, 8}, 10);
 
        </font><font><i>// four missing number</i></font><font>
        pr<b>int</b>MissingNumber(<b>new</b> <b>int</b>[]{1, 2, 3, 4, 9, 8}, 10);
 
        </font><font><i>// Only one missing number in array</i></font><font>
        <b>int</b>[] iArray = <b>new</b> <b>int</b>[]{1, 2, 3, 5};
        <b>int</b> missing = getMissingNumber(iArray, 5);
        System.out.printf(</font><font>"Missing number in array %s is %d %n"</font><font>, 
                           Arrays.toString(iArray), missing);
    }
   </font><font><i>/**    
* A general method to find missing values from an integer array in Java.    
* This method will work even if array has more than one missing element.
*/</i></font><font>
    <b>private</b> <b>static</b> <b>void</b> pr<b>int</b>MissingNumber(<b>int</b>[] numbers, <b>int</b> count) {
        <b>int</b> missingCount = count - numbers.length;
        BitSet bitSet = <b>new</b> BitSet(count);
 
        <b>for</b> (<b>int</b> number : numbers) {
            bitSet.set(number - 1);
        }
 
        System.out.printf(</font><font>"Missing numbers in integer array %s, with total number %d is %n"</font><font>,
        Arrays.toString(numbers), count);
        <b>int</b> lastMissingIndex = 0;

        <b>for</b> (<b>int</b> i = 0; i < missingCount; i++) {
            lastMissingIndex = bitSet.nextClearBit(lastMissingIndex);
            System.out.println(++lastMissingIndex);
        }
 
    }
   </font><font><i>/**    
* 在数组中查找缺失数的 java方法
* 仅1到n之间的数字.    
* 可用于查找整数数组中缺少的元素
*数字从1到100或1-1000    
*/</i></font><font>
    <b>private</b> <b>static</b> <b>int</b> getMissingNumber(<b>int</b>[] numbers, <b>int</b> totalCount) {
        <b>int</b> expectedSum = totalCount * ((totalCount + 1) / 2);
        <b>int</b> actualSum = 0;
        <b>for</b> (<b>int</b> i : numbers) {
            actualSum += i;
        }
 
        <b>return</b> expectedSum - actualSum;
    }
 
}
</font>

Missing numbers in integer array [1, 2, 3, 4, 6], with total number 6 is
5
Missing numbers in integer array [1, 2, 3, 4, 6, 7, 9, 8, 10], with total number 10 is
5
Missing numbers in integer array [1, 2, 3, 4, 6, 9, 8], with total number 10 is
5
7
10
Missing numbers in integer array [1, 2, 3, 4, 9, 8], with total number 10 is
5
6
7
10
Missing number in array [1, 2, 3, 5] is 4