Algos 101: Tìm số nguyên bị thiếu tại vị trí K trong mảng đã sắp xếp

Hôm nay mình muốn giới thiệu với các bạn một bài toán nhỏ nhưng rất có giá trị trong việc rèn luyện khả năng phân tích và giải quyết vấn đề.
Bài toán này cũng có nhiều ứng dụng trong thực tế, chẳng hạn như :

• Kiểm tra xem trong 1 chuỗi giao dịch có thứ tự, tìm mã bị thiếu K .

• Tìm nhanh mã sản phẩm còn thiếu trong hệ thống

Bài toán:

Cho một mảng arr gồm các số nguyên dương được sắp xếp theo thứ tự tăng dần nghiêm ngặt và một số nguyên k.

Hãy tìm và trả về số nguyên dương thứ k bị thiếu trong mảng này.

Ví dụ 1:

• Đầu vào: arr = [2, 3, 4, 7, 11], k = 5

• Đầu ra: 9

• Giải thích: Các số nguyên dương bị thiếu là [1, 5, 6, 8, 9, 10, 12, 13,...]. Số bị thiếu thứ 5 là 9.

Ví dụ 2:

• Đầu vào: arr = [1, 2, 3, 4], k = 2

• Đầu ra: 6

• Giải thích: Các số nguyên dương bị thiếu là [5, 6, 7,...]. Số bị thiếu thứ 2 là 6.

Tiếp cận đơn giản với Vét cạn (BruteForce)

Một cách đơn giản nhất mà ai cũng sẽ nghĩ đến đầu tiên đó là BruteForce (vét cạn) , cách làm này khá đơn giản và trực quan.

1. Mình có thể đếm từ số 1 trở đi

2. với mỗi số đếm ở trên , duyệt qua mảng để kiểm tra xem số hiện tại có nằm trong mảng hay không, nếu không, tăng biến missing_count lên 1.

3. Tăng số đếm lên 1 và lặp lại quá trình trên.

Đánh giá: Tuy cách làm này khá dễ thực hiện, nhưng rất chậm, đặc biệt với tập dữ liệu lớn và k lớn. độ phức tạp: O(k * n) ?

def findKPositive(arr: List[int], k:int):
    missing_count = 0
    curr = 1
    while missing_count != k:
        found = False
        for nu in arr:
            if nu == curr: # phần tử có trong mảng
                found = True
                break
        if not found: missing_count+=1
        curr+=1 
    return curr - 1 # when missing_count == k, số trước đó chính là số thứ k. còn thiếu.

Cải thiện thuật toán Bruteforce

Trong thuật toán bên trên, có 1 bottleneck đó là khi chúng ta kiểm tra số X có ở trong mảng hay không thì chúng ta phải duyệt toàn bộ mảng n lần (n là số phần tử có trong mảng).

Để kiểm tra 1 phần tử có trong mảng hay không, thay vì duyệt qua hết các phần tử trong mảng, chúng ta có thể sử dụng Hash set như bên dưới.

def findKPositive(arr: List[int], k:int):
    missing_count = 0
    curr = 1
    s = set(arr)
    while missing_count != k:
        if curr not in arr: missing_count+=1
        curr+=1
    return curr - 1 # when missing_count == k, số trước đó chính là số thứ k. còn thiếu.

Trong cách tiếp cận Brute Force thông thường, thuật toán có độ phức tạp là O(k*n)Với cách dùng Hash Set, chúng ta đã đưa nó về O(k) . Tuy nhiên, hãy tưởng tượng nếu mảng arr chỉ có vài phần tử nhưng k lại lên tới 1 tỷ? Việc tiếp tục vòng lặp để đếm từng đơn vị cho đến khi chạm mốc k sẽ cực kỳ lãng phí tài nguyên CPU.

Ý tưởng tối ưu: Khi biến curr (số đang xét) đã vượt qua giá trị lớn nhất trong mảng (arr[n-1]Chúng ta biết chắc chắn rằng từ đây trở đi sẽ không còn số nào xuất hiện trong mảng nữa. Thay vì tiếp tục đếm "thủ công", ta có thể dùng một phép tính để "nhảy" thẳng đến kết quả.

Thuật toán cải tiến

1. Duyệt mảng: Chạy vòng lặp và tăng curr như bình thường.

2. Điều kiện dừng sớm (Prune): Nếu curr > max(arr), ta dừng vòng lặp ngay lập tức.

3. Tính toán kết quả tức thì: Tại thời điểm dừng, ta đã có:

   • missing_count: Số lượng số bị thiếu đã tìm được cho đến nay.

   • curr: Giá trị hiện tại bắt đầu vượt quá mảng.

Số lượng số còn lại cần phải tìm thêm là: k - missing_count

Vì kể từ curr trở đi không còn số nào bị chặn nữa, kết quả sẽ là:

Kết quả = k - missing_count + (curr - 1)

def findKPositive(arr: List[int], k:int):
    missing_count = 0
    curr = 1
    s = set(arr)
    while curr <= arr[-1] and missing_count != k:
        if curr not in arr: missing_count+=1
        curr+=1
    return k - missing_count + curr - 1

Đến đây thì các bạn thấy là thuật toán chạy tốt, độ phức tạp : O(n), bộ nhớ sử dụng thêm: O(n). Nhưng thực sự thì chúng ta có thể làm tốt hơn rất nhiều.
Chúng ta có thể thực thi thuật toán này với độ phức tạp O(logn) và không cần phải sử dụng thêm bộ nhớ.

Aha moment !!!

Hãy cùng quan sát mảng arr = [2, 3, 4, 7, 11]. Nếu đây là một mảng hoàn hảo không thiếu số nào, nó sẽ trông như sau:

Phân tích:

• Tại i = 0: Giá trị là 2, nhưng kỳ vọng là 1. Vậy thiếu 2 - 1 = 1 số (số 1).

• Tại i = 3: Giá trị là 7, nhưng kỳ vọng là 4. Vậy trước vị trí này đã thiếu 7 - 4 = 3 số (các số 1, 5, 6).

Công thức vàng: Số lượng số bị thiếu tính đến chỉ số i là:
missing_count = arr[i] - (i + 1)

Chiến thuật: Tìm kiếm Nhị phân (Binary Search)

Vì mảng đã được sắp xếp, hàm missing_count của chúng ta cũng sẽ tăng dần. Thay vì đi bộ từng bước O(n), ta có thể "nhảy cách" bằng Tìm kiếm nhị phân để tìm vị trí mà tại đó số lượng số bị thiếu vừa đủ hoặc vượt qua k.

Các bước thực thi:

1. Khởi tạo left = 0, right = len(arr) - 1.

2. Khi left <= right:

   • Tính trung điểm mid = (left + right) // 2.

   • Tính số lượng số bị thiếu tại mid: missing = arr[mid] - (mid + 1).

   • Nếu missing < k: Nghĩa là số bị thiếu thứ $k$ nằm ở phía bên phải, ta thu hẹp phạm vi: left = mid + 1.

   • Ngược lại: Số đó nằm ở bên trái hoặc chính là vị trí này: right = mid - 1.

kết quả cuối cùng

Sau khi vòng lặp kết thúc, vị trí right là chỉ số cuối cùng mà số lượng số bị thiếu vẫn còn nhỏ hơn $k$. Số chúng ta cần tìm sẽ được tính từ giá trị tại right cộng thêm phần còn thiếu:

Kết quả = arr[right] + k - Missing(right)

Thay công thức Missing(right) = arr[right] - (right + 1) vào, ta có:

Kết quả = arr[right] + k - (arr[right] - (right + 1) = k + right + 1

Vì khi kết thúc vòng lặp, left = right + 1, nên công thức rút gọn cực kỳ đẹp mắt là:

Kết quả=left + k

def find_kth_positive(arr, k):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        # Tính số lượng số bị thiếu tính đến vị trí mid
        missing = arr[mid] - (mid + 1)
        
        if missing < k:
            left = mid + 1
        else:
            right = mid - 1
            
    # Kết quả cuối cùng
    return left + k

Kết luận

Đừng vội vàng gõ những dòng code đầu tiên ngay khi vừa đọc xong đề bài. Bí quyết của một lập trình viên giỏi không nằm ở tốc độ viết code, mà ở khả năng quan sát đặc điểm dữ liệu.

Như chúng ta đã thấy qua bài toán trên:

• Nếu dữ liệu xáo trộn, ta dùng sức mạnh của Hash Set hoặc vét cạn.

• Nếu dữ liệu đã sắp xếp, ta tận dụng mối liên hệ giữa chỉ số (index) và giá trị để đột phá với tìm kiếm nhị phân.

Việc phân tích kỹ lưỡng giúp bạn không chỉ giải quyết được bài toán mà còn tìm ra giải pháp "thông minh" nhất. Hãy luôn bắt đầu từ những cách tiếp cận đơn giản nhất, hiểu rõ từng bước đi, rồi dần dần tối ưu hóa. Đó chính là lộ trình để bạn đạt được khoảnh khắc "AHA!" – khi mọi nút thắt logic được tháo gỡ và bạn thực sự làm chủ được thuật toán của chính mình.