How to find out missing number in Integer Array Java

Hôm nay rảnh, sau thời gian đau đầu với tiếng Nhật thì hôm nay mò lại với Java Nhớ lại hồi còn sinh viên có một câu phỏng vấn của thằng bạn, thấy cũng hay. Đề bài như thế này:

Cho một mảng số nguyên liên tiếp, sắp xếp tăng đần n phần tử, giá trị bắt đầu từ 0. Nhưng vì một lý do nào đó mà phần có một phần tử bị thiếu, nên chỉ còn n-1 phần tử. Tìm phần tử bị thiếu đó. Ví dụ mảng số nguyên: {1,2,3,4,6,7,8,9,10,11} thì số bị thiếu sẽ là 5.

Rất nhiều bạn sẽ tìm ra được cách đơn giản cho bài này như sau:

1. Tính tổng tất cả các phần tử trong mảng đó, đặt là sum
2. Ta nhận thấy tổng tất cả các số nguyên liên tiếp từ 0->n là n*(n+1)/2.
3. Vậy số bị thiếu sẽ là n*(n+1)/2 - sum.

Cài đặt trên Java như sau:

    import java.util.Arrays;

    public class Main {

    public static void main(String[] args) {
        int[] numbers = new int[]{1, 2, 3, 4, 6, 7, 8, 9, 10, 11};
        System.out.printf("Missing number in array %s is %d", Arrays.toString(numbers), getMissingNumber(numbers, 11));
    }

    private static int getMissingNumber(int[] numbers, int length) {
        int expectedSum = length * (length + 1) / 2;
        int actualSum = 0;
        for (int i : numbers) {
            actualSum += i;
        }
        return expectedSum - actualSum;
    }
}

Câu trả lời trên sẽ đúng nếu mảng chỉ thiếu một phần tử, còn thiếu nhiều hơn 1 phần tử thì sao?

Huh? Thiếu nhiều hơn 1 phần tử à? Khó nha...

Ah, Anh ơi, em nghĩ ra rồi, em sẽ dùng một mảng để đánh dấu các phần tử bị mất đi.

Cài đặt thế nào em?

Em sẽ dùng BitSet, bla bla...

Giờ thì tìm hiểu BitSet là cái củ cải gì nào.

This class implements a vector of bits that grows as needed. Each component of the bit set has a boolean value.

À đây rồi, còn gì dễ dàng hơn để đánh giấu các phần tử chỉ có 2 giá trị missing, và non-missing là dùng một mảng các bits có giá trị true và false? Ok, giờ thì đọc các phương thức của nó:

    BitSet(int nbits)
    /*Creates a bit set whose initial size is large enough to explicitly represent bits with indices in the range 0 through nbits-1.*/

Ok. trong trường hợp của chúng ta sẽ là:

    BitSet bitSet = new BitSet(length);

Phía trên là tạo ra một bitSet để chứa, chúng ta vẫn chưa khởi tạo các giá trị cho nó, để khởi tạo giá trị cho nó BitSet class cung cấp phương thức:

    void set(int bitIndex)
    /*Sets the bit at the specified index to true.*/

Ok, ban đầu coi như tất cả các giá trị đều là non-missing, tương ứng với true.

for (int number: numbers){
    bitSet.set(number-1);
}

Giờ là lúc quan trọng nhất, tìm các phần tử missing, do ở trên chúng ta thực hiện duyệt các phần tử, nếu phần tử nào bị missing thì nó sẽ có giá trị là false. Chúng ta cần 1 phương thức nữa của BitSet class.

int nextClearBit(int fromIndex)
/*Returns the index of the first bit that is set to false that occurs on or after the specified starting index.*/

Cài đặt như sau:

    int missingCount = length- numbers.length;
    /*xác định số phần tử bị thiếu*/
    int lastMissingIndex = 0;
    /*duyệt phần tử bị thiếu từ 0 trở đi*/
    for(int i = 0; i < missingCount; i++){
        lastMissingIndex = bitSet.nextClearBit(lastMissingIndex);
        /*lần lượt in ra các phần tử có bitset = false*/
        System.out.println(++lastMissingIndex);
    }

Code hoàn chỉnh:

import java.util.Arrays;
import java.util.BitSet;

public class Main {

    public static void main(String[] args) {
        int[] numbers = new int[]{1, 2, 3, 4, 6, 7, 9, 10, 11};
        getMissingNumber(numbers, 11);
    }

    private static void getMissingNumber(int[] numbers, int length) {
        int missingCount = length - numbers.length;
        BitSet bitSet = new BitSet(length);
        for (int number : numbers) {
            bitSet.set(number - 1);
        }
        int lastMissingIndex = 0;
        System.out.printf("Missing number in integer array %s, with total number %d is: ", Arrays.toString(numbers), length);
        for (int i = 0; i < missingCount; i++) {
            lastMissingIndex = bitSet.nextClearBit(lastMissingIndex);
            System.out.println(++lastMissingIndex);
        }
    }
}

Output:

Missing number in integer array [1, 2, 3, 4, 6, 7, 9, 10, 11], with total number 11 is:

5

8