Làm thế nào để bạn tìm thấy số còn thiếu trong chuỗi python?

Đưa ra một danh sách với các số được sắp xếp, chúng tôi muốn tìm ra những số nào bị thiếu trong phạm vi số đã cho

với phạm vi

chúng ta có thể thiết kế một vòng lặp for để kiểm tra phạm vi số và sử dụng điều kiện if với toán tử not in để kiểm tra các phần tử còn thiếu

Giả sử chúng ta có một danh sách các số được gọi là nums kích thước n trong đó tất cả các số trong danh sách đều có mặt trong khoảng [1, n] một số phần tử có thể xuất hiện hai lần trong khi những phần tử khác chỉ xuất hiện một lần. Ta phải tìm tất cả các số từ [1, n] sao cho chúng không có trong danh sách. Chúng ta phải trả về các số được sắp xếp theo thứ tự tăng dần. Chúng ta phải cố gắng tìm một giải pháp có thời gian tuyến tính và không gian không đổi

Vì vậy, nếu đầu vào là [4, 4, 2, 2, 6, 6], thì đầu ra sẽ là [1, 3, 5]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• mảng. = một mảng có kích thước nums + 1 và điền vào 0
• cho mỗi i trong nums, làm
• còn thiếu. = một danh sách mới
• đối với tôi trong phạm vi từ 0 đến kích thước của mảng, hãy làm
  • nếu arr[i] bằng 0 và tôi không bằng 0, thì
    • chèn i vào cuối thiếu
• trở lại mất tích

Chúng ta hãy xem triển khai sau đây để hiểu rõ hơn -

Thí dụ

Bản thử trực tiếp

class Solution:
   def solve(self, nums):
      arr = [0]*(len(nums)+1)
      for i in nums:
         arr[i] += 1
      missing = []
      for i in range(len(arr)):
         if arr[i] == 0 and i != 0:
            missing.append(i)
      return missing
ob = Solution()
print(ob.solve([4, 4, 2, 2, 6, 6]))

Đầu vào

[4, 4, 2, 2, 6, 6]

đầu ra

[1, 3, 5]

Công cụ sau đây trực quan hóa những gì máy tính đang làm từng bước khi nó thực thi chương trình nói trên

Trình chỉnh sửa mã Python

Đóng góp mã và nhận xét của bạn thông qua Disqus

Trước. Viết chương trình Python để tìm một số còn thiếu trong danh sách
Kế tiếp. Viết chương trình Python để tìm ba số từ một mảng sao cho tổng của ba số bằng 0

Mức độ khó của bài tập này là gì?

Kiểm tra kỹ năng Lập trình của bạn với bài kiểm tra của w3resource

Theo dõi chúng tôi trên Facebook và Twitter để cập nhật thông tin mới nhất.

con trăn. Lời khuyên trong ngày

Quản lý bộ nhớ

getrefcount sẽ hiển thị số lần một đối tượng được sử dụng trong bộ nhớ. Đó là một công cụ tuyệt vời có thể được sử dụng để quản lý bộ nhớ trong bất kỳ chương trình nào và nó cũng rất tiện lợi

Getrefcount sẽ tính toán mức sử dụng đối tượng ở mức ByteCode thấp để nó có thể có xu hướng cao hơn dự kiến. Ví dụ: khi bạn in một giá trị, giá trị đó thực sự được xử lý nhiều lần ở chế độ nền bên trong chính hàm in và getrefcount cũng đếm phiên bản khi giá trị đó được gọi bằng chính phương thức getrefcount. Vì vậy, thật an toàn khi nói rằng số lượng thực tế sẽ luôn cao hơn ít nhất 1 lần so với dự kiến

Nếu trình tự đầu vào được sắp xếp, bạn có thể sử dụng bộ tại đây. Lấy giá trị bắt đầu và kết thúc từ danh sách đầu vào

def missing_elements(L):
    start, end = L[0], L[-1]
    return sorted(set(range(start, end + 1)).difference(L))

Điều này giả sử Python 3;

Cuộc gọi sorted() là tùy chọn;

Thử nghiệm

>>> L = [10,11,13,14,15,16,17,18,20]
>>> missing_elements(L)
[12, 19]

Một cách tiếp cận khác là phát hiện khoảng cách giữa các số tiếp theo;

from itertools import islice, chain

def window(seq, n=2):
    "Returns a sliding window (of width n) over data from the iterable"
    "   s -> (s0,s1,...s[n-1]), (s1,s2,...,sn), ..                   "
    it = iter(seq)
    result = tuple(islice(it, n))
    if len(result) == n:
        yield result    
    for elem in it:
        result = result[1:] + (elem,)
        yield result

def missing_elements(L):
    missing = chain.from_iterable(range(x + 1, y) for x, y in window(L) if (y - x) > 1)
    return list(missing)

Đây là thao tác O(n) thuần túy và nếu bạn biết số lượng mục bị thiếu, bạn có thể đảm bảo rằng nó chỉ tạo ra những mục đó rồi dừng lại

Có nhiều cách để giải quyết vấn đề này bằng Python. Trong bài viết này, chúng tôi sẽ đề cập đến những điều đơn giản nhất

thuật toán

Bước 1. Tạo một mảng trống cho các mục bị thiếu

Bước 2. Lặp qua các phần tử trong phạm vi của phần tử đầu tiên và cuối cùng của mảng

Bước 3. So sánh biến vòng lặp với mảng đã cho nếu giá trị không xuất hiện, hãy thêm nó vào mảng bị thiếu

Ghi chú. Mảng phải được sắp xếp để làm việc này. Sử dụng arr.sort() trên một mảng chưa sắp xếp trước khi đưa nó vào chương trình

Giải pháp 1

arr = [1,2,3,4,5,6,7,9,10]
missing_elements = []
for ele in range(arr[0], arr[-1]+1):
    if ele not in arr:
        missing_elements.append(ele)
print(missing_elements)

đầu ra

2. Sử dụng danh sách hiểu

arr = [1,2,3,4,5,7,6,9,10]
missing_elemnts = [item for item in range(arr[0], arr[-1]+1) if item not in arr]
print(missing_elemnts)

đầu ra

Sử dụng khả năng hiểu danh sách, chúng tôi gói gọn giải pháp trên trong một dòng

3. Sử dụng Bộ()

________ 16 ________ là kiểu dữ liệu có thể thay đổi không theo thứ tự của Python chỉ chứa các giá trị duy nhất

arr = [1,2,3,4,5,7,6,9,10]
missing_value = set(range(arr[0], arr[-1]+1)) - set(arr)
print(missing_value)

đầu ra

{8}

Ở đây, chúng tôi đã tạo một đối tượng tập hợp có các giá trị trong phạm vi giá trị ban đầu và giá trị cuối cùng của mảng được cung cấp, sau đó so sánh nó với mảng được cung cấp để lấy giá trị còn thiếu