Với danh sách số nguyên không theo thứ tự, trả lại giá trị không có trong danh sách

Question

Tôi gặp vấn đề về thuật toán mà tôi gặp phải nhưng không thể đưa ra giải pháp thỏa đáng. Tôi duyệt diễn đàn này một số và gần nhất tôi đã đến cùng một vấn đề là How to find a duplicate element in an array of shuffled consecutive integers?.

Tôi có một danh sách các phần tử N của các số nguyên có thể chứa các phần tử 1-M (M> N), hơn nữa danh sách không được phân loại. Tôi muốn một hàm sẽ lấy danh sách này làm đầu vào và trả về một giá trị trong phạm vi 1-M không có trong danh sách. Danh sách không chứa trùng lặp. Tôi đã hy vọng cho một giải pháp o (N), với việc sử dụng thêm không gian CẬP NHẬT: chức năng không thể thay đổi danh sách gốc L

Ví dụ N = 5 M = 10 Danh sách (L): 1, 2, 4, 8, 3 rồi f (L) = 5 Thành thật mà nói, tôi không quan tâm nếu nó trả về một phần tử không phải là 5, chỉ miễn là nó đáp ứng các giới hạn trên

Giải pháp duy nhất tôi đã đưa ra cho đến nay đang sử dụng mảng M khác. Đi qua danh sách đầu vào và thiết lập các phần tử mảng tương ứng thành 1 nếu có trong danh sách. Sau đó lặp lại trong danh sách này một lần nữa và trả về chỉ số của phần tử đầu tiên với giá trị 0. Như bạn có thể thấy điều này sử dụng không gian bổ sung o (M) và có độ phức tạp 2 * o (N). Bất kỳ trợ giúp nào chúng tôi sẽ đánh giá cao.

Cảm ơn sự giúp đỡ của mọi người. Cộng đồng tràn ngăn xếp chắc chắn là siêu hữu ích. Để cung cấp cho mọi người thêm một chút ngữ cảnh về vấn đề tôi đang cố giải quyết. Tôi có một bộ mã thông báo M mà tôi đưa ra cho một số khách hàng (một cho mỗi khách hàng). Khi một khách hàng được thực hiện với các mã thông báo họ nhận được trả lại cho đống của tôi. Như bạn có thể thấy thứ tự ban đầu tôi cung cấp cho khách hàng một mã thông báo được sắp xếp.
nên M = 3         Tokens
client1: 1                 < 2,3>
client2: 2                 < 3>
client1 trở lại: 1     < 1,3>
khách hàng 3: 3             < 1>
Bây giờ câu hỏi được đưa ra client4 mã thông báo 1. Tôi có thể ở giai đoạn này cung cấp cho khách hàng 4 thẻ 2 và sắp xếp danh sách. Không chắc chắn nếu điều đó sẽ giúp. Trong bất kỳ trường hợp nào nếu tôi nghĩ ra một giải pháp sạch sẽ, tôi chắc chắn sẽ đăng nó
Chỉ cần nhận ra rằng tôi có thể đã nhầm lẫn mọi người. Tôi không có danh sách mã thông báo miễn phí với tôi khi tôi được gọi. Tôi có thể duy trì tĩnh danh sách như vậy nhưng tôi không muốn

Answer 1

Bạn có thể có O (N) thời gian và không gian. Bạn có thể chắc chắn có một phần tử vắng mặt trong phạm vi 1..N + 1, do đó hãy tạo một mảng các phần tử N + 1 và bỏ qua các số lớn hơn N + 1.

Nếu M lớn hơn N, giả sử M> 2N, tạo số ngẫu nhiên trong 1.M và kiểm tra xem nó có nằm trong danh sách trong khoảng thời gian O (N), không gian O (1) không. Xác suất bạn sẽ tìm thấy một giải pháp trong một lần vượt qua ít nhất là 1/2, và do đó (phân bố hình học) số lần vượt qua dự kiến ​​là không đổi, độ phức tạp trung bình O (N).

Nếu M là N + 1 hoặc N + 2, hãy sử dụng phương pháp được mô tả here.

Answer 2

Bạn có thể làm điều gì đó như một loại đếm không? Tạo một mảng có kích thước (M-1) sau đó đi qua danh sách một lần (N) và thay đổi phần tử mảng được lập chỉ mục tại i-1 thành một. Sau khi lặp một lần qua N, tìm kiếm 0 -> (M-1) cho đến khi bạn tìm thấy mảng đầu tiên có giá trị bằng không.

Tôi có nên O (N + M) không.

Mảng L có kích thước (M-1): [0 = 0, 1 = 0, 2 = 0, 3 = 0, 4 = 0, 5 = 0, 6 = 0, 7 = 0, 8 = 0 , 9 = 0]

Sau khi lặp qua các phần tử N: [0 = 1, 1 = 1, 2 = 1, 3 = 1, 4 = 0, 5 = 0, 6 = 0, 7 = 1, 8 = 0, 9 = 0]

Tìm kiếm mảng 0 -> (M-1) tìm thấy chỉ số 4 là số không, do đó 5 (4 + 1) là số nguyên đầu tiên không phải ở L.

Answer 3

Bạn có thể chia và chinh phục. Về cơ bản được đưa ra phạm vi 1..m, làm một phong cách quicksort trao đổi với m/2 là trục. Nếu có ít hơn m/2 phần tử trong nửa đầu, sau đó có một số bị thiếu và lặp đi lặp lại tìm thấy nó. Nếu không, có một số bị mất trong nửa thứ hai. Mức độ phức tạp: n + n/2 + n/4 ... = O (n)

def findmissing(x, startIndex, endIndex, minVal, maxVal): 
    pivot = (minVal+maxVal)/2 
    i=startIndex 
    j=endIndex 
    while(True): 
     while((x[i] <= pivot) and (i<j)): 
      i+=1 
     if i>=j: 
      break 
     while((x[j] > pivot) and (i<j)): 
      j+=1 
     if i>=j: 
      break 
     swap(x,i,j) 
    k = findlocation(x,pivot) 
    if (k-startIndex) < (pivot-minVal): 
     findmissing(x,startIndex, k, minVal, pivot) 
    else: 
     findmissing(x, k+1, endIndex, pivot+1, maxVal) 

Tôi chưa thực hiện điều kiện kết thúc mà tôi sẽ để lại cho bạn.

Answer 4

Sau khi đọc cập nhật của bạn, tôi đoán bạn đang làm cho nó quá phức tạp. Trước hết hãy để tôi liệt kê ra những gì tôi nhận được từ câu hỏi của bạn

• yoou cần phải cung cấp một mã thông báo cho khách hàng không phân biệt thứ tự của nó, trích dẫn từ bài gốc của bạn

ví dụ N = 5 M = 10 Danh sách (L): 1, 2, 4, 8, 3 rồi f (L) = 5 Để là trung thực tôi không quan tâm nếu nó trả về một phần tử khác 5, chỉ cần dài vì nó đáp ứng các hạn chế trên

• Thứ hai, bạn đã mantaining một danh sách các "M" tokens
• Khách hàng được lấy token và sau khi sử dụng nó trở về nó lại cho bạn

Với những 2 điểm, tại sao bạn không thực hiện một TokenPool?

• Thực hiện danh sách M của bạn dựa trên một Queue
• Bất cứ khi nào một khách hàng yêu cầu một một mã thông báo, lấy một mã thông báo từ hàng đợi nghĩa là loại bỏ nó từ hàng đợi. Bằng phương pháp này, hàng đợi của bạn sẽ luôn duy trì các mã thông báo không được cung cấp. bạn đang làm điều đó O (1)
• Bất cứ khi nào một khách hàng được thực hiện với mã thông báo, họ sẽ trả lại cho bạn. Thêm nó trở lại hàng đợi. Một lần nữa O (1).

Thực hiện toàn bộ, bạn sẽ không phải lặp qua bất kỳ danh sách nào. Tất cả những gì bạn phải làm là Tạo mã thông báo và chèn vào hàng đợi.