Xác định giá trị sẵn có đầu tiên trong danh sách các số nguyên

Question

Tôi nhận được một Danh sách đơn giản của int.

List<int> myInts = new List<int>(); 

myInts.Add(0); 
myInts.Add(1); 
myInts.Add(4); 
myInts.Add(6); 
myInts.Add(24); 

Mục tiêu của tôi là lấy giá trị chưa sử dụng đầu tiên (có sẵn) từ Danh sách.

(giá trị tích cực đầu tiên đó là chưa có mặt trong bộ sưu tập)

Trong trường hợp này, câu trả lời sẽ là 2.

Đây là mã hiện tại của tôi:

int GetFirstFreeInt() 
{ 
    for (int i = 0; i < int.MaxValue; ++i) 
    { 
     if(!myInts.Contains(i)) 
      return i; 
    } 

    throw new InvalidOperationException("All integers are already used."); 
} 

Có cách tốt hơn? Có thể sử dụng LINQ? Bạn sẽ làm điều này như thế nào?

Tất nhiên ở đây tôi sử dụng ints cho đơn giản nhưng câu hỏi của tôi có thể áp dụng cho bất kỳ loại nào.

Answer 1

Bạn về cơ bản muốn phần tử đầu tiên từ chuỗi 0..int.MaxValue mà không được chứa trong myInts:

int? firstAvailable = Enumerable.Range(0, int.MaxValue) 
           .Except(myInts) 
           .FirstOrDefault(); 

Chỉnh sửa để đáp ứng với bình luận:

Có không hiệu suất phạt vào đây để lặp tối đa int.MaxValue. Những gì LINQ sẽ thực hiện trong nội bộ là tạo ra hashtable cho myInts và sau đó bắt đầu lặp qua chuỗi được tạo bởi Enumerable.Range() - khi mục đầu tiên không chứa trong hashtable được tìm thấy rằng số nguyên được mang theo phương pháp Except() và trả về FirstOrDefault() - sau đó lặp lại dừng lại. Điều này có nghĩa là nỗ lực tổng thể là O (n) để tạo ra hashtable và sau đó trường hợp xấu nhất O (n) cho iterating qua chuỗi trong đó n là số nguyên trong myInts.

Để biết thêm về Except() thấy loạt EduLinq ví dụ: Jon Skeet: Reimplementing LINQ to Objects: Part 17 - Except

Answer 2

Vâng, nếu danh sách được đặt hàng từ nhỏ nhất đến lớn nhất và chứa các giá trị từ 0 đến vô cùng tích cực, bạn có thể chỉ đơn giản là truy cập vào phần tử thứ i. if (myInts[i] != i) return i; mà về cơ bản là giống nhau, nhưng không cần lặp lại qua danh sách cho mỗi và mọi kiểm tra Contains (phương pháp Chứa lặp qua danh sách, chuyển thuật toán của bạn thành O (n-bình phương) thay vì O (n)) .