Bài toán:

Tìm các số bị thiếu trong khoảng từ 1 đến 100 (hoặc một phạm vi lớn hơn)Ví dụ: Tìm các số còn thiếu trong phạm vi từ 1 đến 10. Giả sử dãy số đầy đủ là 1, 2, 3, 4, 5, 6, 7, 8, 9, 10; bạn cần xác định xem số nào không xuất hiện trong mảng cho trước.
Cách giải và độ phức tạp của bài toán này sẽ thay đổi tùy thuộc vào việc số lượng số bị thiếu là một số hay nhiều số. Việc các số trong mảng có được sắp xếp hay không thường không quá quan trọng. Do đó, nếu gặp câu hỏi này khi phỏng vấn, trước tiên bạn nên hỏi rõ xem có bao nhiêu số bị thiếu.

1. Trường hợp thiếu một số duy nhất.

Nếu chỉ thiếu một số, lời giải cực kỳ đơn giản vì chúng ta có thể áp dụng công thức toán học tính tổng dãy số liên tiếp:
$$S = frac{n(n + 1)}{2}$$

Cách làm:

  1. Tính tổng kỳ vọng (expectedSum) bằng công thức trên.
  2. Tính tổng thực tế (actualSum) của các phần tử có trong mảng.
  3. Hiệu số (expectedSum - actualSum) chính là số bị thiếu.
Để tính tổng thực tế, chúng ta cần duyệt qua mảng một lần, vì vậy độ phức tạp thời gian là $O(n)$.
Mã nguồn minh họa:
Phiên bản trước Java 8:
private static int findMissingNumber(int[] numbers, int totalCount) {
    int expectedSum = totalCount * (totalCount + 1) / 2;
    int actualSum = 0;
    for(int i : numbers) {
        actualSum += i;
    }
    return expectedSum - actualSum;
}
Phiên bản từ Java 8 trở về sau:
private static int findMissingNumber(int[] numbers, int totalCount) {
    int expectedSum = totalCount * (totalCount + 1) / 2;
    int actualSum = Arrays.stream(numbers).reduce(Integer::sum).getAsInt();

    return expectedSum - actualSum;
}

2. Trường hợp thiếu nhiều số (từ hai số trở lên)Khi có nhiều hơn một số bị thiếu, việc tìm kiếm sẽ trở nên phức tạp hơn và có nhiều cách tiếp cận khác nhau. Một trong những phương pháp hiệu quả là sử dụng BitSet. Để hiểu cách này, bạn cần nắm rõ đặc điểm của lớp BitSet trong Java.BitSet có thể coi là một mảng các giá trị boolean (true/false). Thuật toán hoạt động như sau:

  1. Duyệt qua mảng cho trước ($N$ phần tử) và đánh dấu true tại vị trí tương ứng trong BitSet.
  2. Sau đó, tìm các vị trí vẫn đang mang giá trị false (chính là các số bị thiếu) trong phạm vi tổng số lượng phần tử ($T$).
  3. Độ phức tạp thời gian ước tính là $O(N + K)$ (trong đó $K$ là số lượng số bị thiếu).
Lưu ý:
$N$: Số lượng phần tử hiện có trong mảng.
$K$: Số lượng phần tử bị thiếu ($K = T - N$).
Trong trường hợp xấu nhất, $K$ có thể tương đương với $N$.
Mã nguồn minh họa sử dụng BitSet:
private static int[] findMissingNumbers(int[] numbers, int totalCount) {
    int missingCount = totalCount - numbers.length;
    BitSet bitSet = new BitSet(totalCount);
    
    // Đánh dấu các số đã xuất hiện (Lặp N lần)
    for (int number : numbers) {
        bitSet.set(number - 1, true);
    }
    
    int lastMissingIndex = 0;
    int[] missingNumbers = new int[missingCount];
    
    // Tìm các vị trí bị thiếu (Lặp K lần)
    for (int i = 0; i < missingCount; i++) {
        // Tìm giá trị false đầu tiên tính từ lastMissingIndex
        lastMissingIndex = bitSet.nextClearBit(lastMissingIndex);
        missingNumbers[i] = ++lastMissingIndex;
    }
    return missingNumbers;
}
Nguồn bài viết ryukato.github.io