Viết chương trình tìm số bị thiếu trong danh sách đã sắp xếp bằng Python

Đề bài: Cho một danh sách (list) các số nguyên đã được sắp xếp nhưng bị thiếu một vài số nguyên, viết một chương trình Python để tìm tất cả số nguyên còn thiếu.

Ví dụ:

Input : [1, 2, 4, 6, 7, 9, 10]
Output : [3, 5, 8]

Input : [5, 6, 10, 11, 13]
Output : [7, 8, 9, 12]

Trong bài viết này, Quản Trị Mạng sẽ cùng với các bạn tìm hiểu cách viết chương trình tìm số bị thiếu trong danh sách đã sắp xếp bằng Python.

Cách 1: Sử dụng List Comprehension

Bạn có thể xử lý vấn đề này với List Comprehension có sẵn của Python. Dưới đây là code mẫu để bạn có thể tham khảo:

# Python3 program to Find missing
# integers in list
         
def find_missing(lst):
    max = lst[0]
    for i in lst :
      if i > max :
        max= i
         
    min = lst [0]
    for i in lst :
      if i < min:
        min = i
    missing = max+1
    list1=[]
 
    for _ in lst :
       
        max = max -1
        if max not in lst :
          list1.append(max)
      
    return list1
 
# Driver code
lst = [1,5,4,6,8, 2,3, 7, 9, 10]
print(find_missing(lst))

Kết quả trả về là:

[3, 5, 8]

Cách 2: Sử dụng List Comprehension với zip()

Vẫn tương tự như cách 1 nhưng bạn sử dụng thêm zip() để rút gọn code lại. Dưới đây là code mẫu:

# Python3 program to Find missing
# integers in list
         
def find_missing(lst):
    return [i for x, y in zip(lst, lst[1:])
        for i in range(x + 1, y) if y - x > 1]
 
# Driver code
lst = [1, 2, 4, 6, 7, 9, 10]
print(find_missing(lst))

Kết quả trả về là:

[3, 5, 8]

Cách 3: Sử dụng set

Sử dụng set của Python là một cách hiệu quả và đơn giản để tìm các số bị thiếu trong danh sách. Chúng ta sẽ chuyển đổi danh sách sang set và chỉ cần xuất ra sự khác biêt giữa set này và set của những số nguyên từ min tới max.

Dưới đây là code mẫu để các bạn tham khảo:

# Python3 program to Find missing
# integers in list
         
def find_missing(lst):
    return sorted(set(range(lst[0], lst[-1])) - set(lst))
 
# Driver code
lst = [1, 2, 4, 6, 7, 9, 10, 12, 13, 15]
print(find_missing(lst))

Kết quả trả về là:

[3, 5, 8, 11, 14]

Cách 4: Sử dụng difference()

Đây là một cách tiếp cận tương tự như cách số 3. Tuy nhiên, có một chút khác biệt là thay vì sử dụng toán tử "-" để tìm sự khác biệt giữa hai set, chúng ta có thể sử dụng phương thức difference() của Python.

Dưới đây là code mẫu:

# Python3 program to Find missing
# integers in list
         
def find_missing(lst):
    start = lst[0]
    end = lst[-1]
    return sorted(set(range(start, end + 1)).difference(lst))
 
# Driver code
lst = [1, 2, 4, 6, 7, 9, 10]
print(find_missing(lst))

Kết quả trả về là:

[3, 5, 8]

Kết luận

Tìm số bị thiếu trong danh sách đã sắp xếp là câu hỏi thường xuyên được các nhà tuyển dụng đưa ra để kiểm tra trình độ của các ứng viên. Quản Trị Mạng hy vọng rằng bài viết này sẽ giúp ích cho các bạn.