Câu hỏi Tìm phần tử duy nhất trong một mảng của một triệu phần tử


Tôi đã được hỏi câu hỏi này trong một cuộc phỏng vấn gần đây.

Bạn được cung cấp một mảng có một triệu phần tử. Tất cả các phần tử là các bản sao trừ một. Nhiệm vụ của tôi là tìm phần tử duy nhất.

var arr = [3, 4, 3, 2, 2, 6, 7, 2, 3........]

Cách tiếp cận của tôi là đi qua toàn bộ mảng trong for lặp lại và sau đó tạo map với chỉ mục là number trong mảng và value như frequency của số xuất hiện trong mảng. Sau đó lặp lại bản đồ của chúng tôi và trả lại chỉ mục có giá trị là 1.

Tôi nói cách tiếp cận của tôi sẽ mất O(n) thời gian phức tạp. Người phỏng vấn nói với tôi để tối ưu hóa nó trong ít hơn O(n) phức tạp. Tôi nói rằng chúng ta không thể, vì chúng ta phải trải qua toàn bộ mảng với hàng triệu yếu tố.

Cuối cùng, anh ta có vẻ không hài lòng và chuyển sang câu hỏi tiếp theo.

Tôi hiểu rằng hàng triệu yếu tố trong mảng là tốn kém, nhưng làm thế nào chúng ta có thể tìm thấy một yếu tố duy nhất mà không thực hiện quét tuyến tính của toàn bộ mảng?

PS: mảng không được sắp xếp.


10
2018-06-03 22:15


gốc


Có điều gì khác mà chúng ta biết về mảng không? Nó được sắp xếp? Chúng ta có biết giá trị duy nhất trong mảng không? Bạn hiện đang chi tiêu 2n thời gian đi qua từng phần tử của mảng và sau đó mỗi khóa của bản đồ và có thể tránh vòng lặp thứ hai bằng cách xóa các khóa khỏi bản đồ khi bạn nhận thấy các bản sao, nhưng O(2n) vẫn còn O(n). - Andrew Rueckert
@AndrewRueckert - nó không được sắp xếp. Mảng chỉ có tất cả các số được lặp lại theo thứ tự ngẫu nhiên, nhưng chỉ một số sẽ không được lặp lại. - Wild Widow
Bạn có chắc họ nói O (n) thời gian phức tạp, thay vì, nói, O (n) không gian phức tạp? Bạn có biết bất cứ điều gì về bao nhiêu bản sao các yếu tố trùng lặp có? - user2357112
@ user2357112 - họ nói thời gian phức tạp, không phải đối phó với không gian phức tạp ở đây. trùng lặp có thể xảy ra bất kỳ số lần nào - Wild Widow
Bạn phải xem xét chính xác tất cả các phần tử n (trường hợp xấu nhất, có thể có trường hợp bạn có thể khấu trừ khác). Người cuối cùng bạn nhìn vào có thể tiết lộ rằng ứng cử viên hiện tại của bạn là một bản sao. Người phỏng vấn có lẽ không hài lòng với lời giải thích của bạn và thử nghiệm bạn. - zapl


Các câu trả lời:


Tôi chắc chắn rằng bạn không thể giải quyết vấn đề này mà không phải trải qua toàn bộ mảng, ít nhất nếu bạn không có bất kỳ thông tin bổ sung nào (như các yếu tố được sắp xếp và giới hạn ở các giá trị nhất định), do đó vấn đề có thời gian tối thiểu sự phức tạp của O(n). Tuy nhiên, bạn có thể giảm độ phức tạp của bộ nhớ xuống O(1) với một giải pháp dựa trên XOR, nếu mọi phần tử nằm trong mảng, thậm chí là số lần, mà dường như là biến thể phổ biến nhất của vấn đề, nếu đó là bất kỳ sự quan tâm nào đối với bạn:

int unique(int[] array)
{
    int unpaired = array[0];
    for(int i = 1; i < array.length; i++)
        unpaired = unpaired ^ array[i];
    return unpaired;
}

Về cơ bản, mọi phần tử XORed đều hủy bỏ phần tử kia, do đó kết quả của bạn là phần tử duy nhất không hủy bỏ.


15
2018-06-03 22:44





Giả sử mảng không được đặt hàng, bạn không thể. Mọi giá trị đều loại trừ lẫn nhau cho cái tiếp theo sao cho không cái gì có thể được suy ra về một giá trị từ bất kỳ giá trị nào khác?

Nếu đó là một mảng giá trị được sắp xếp, thì đó là một vấn đề khác và phụ thuộc hoàn toàn vào thứ tự được sử dụng.

Tôi đồng ý cách dễ nhất là có một thùng chứa khác và lưu trữ tần số của các giá trị.


1
2018-06-03 22:22





Thực tế, vì số lượng phần tử trong mảng đã được sửa, bạn có thể làm tốt hơn nhiều so với những gì bạn đã đề xuất.

Bằng cách "tạo một map với chỉ mục là số trong mảng và giá trị là tần số của số xuất hiện trong mảng ", bạn tạo bản đồ với 2 ^ 32 vị trí (giả sử mảng có số nguyên 32 bit), và sau đó bạn phải vượt qua bản đồ đó để tìm vị trí đầu tiên có giá trị là một. Điều đó có nghĩa là bạn đang sử dụng một không gian phụ trợ lớn và trong trường hợp xấu nhất bạn đang thực hiện trong khoảng  10 ^ 6 + 2 ^ 32 hoạt động (một triệu để tạo bản đồ và 2 ^ 32 để tìm phần tử).

Thay vì làm như vậy, bạn có thể sắp xếp mảng với một số n*log(n) và sau đó tìm kiếm phần tử trong mảng được sắp xếp, vì trong trường hợp của bạn, n = 10^6.

Ví dụ, sử dụng sắp xếp hợp nhất, bạn sẽ sử dụng một không gian phụ nhỏ hơn nhiều (chỉ là một mảng 10 ^ 6 số nguyên) và sẽ thực hiện (10 ^ 6) * log (10 ^ 6) + 10 ^ 6 thao tác để sắp xếp và sau đó tìm phần tử, đó là khoảng 21 * 10 ^ 6 (nhiều lần nhỏ hơn 10 ^ 6 + 2 ^ 32).

PS: sắp xếp mảng giảm tìm kiếm từ bậc hai sang chi phí tuyến tính, bởi vì với mảng được sắp xếp, chúng tôi chỉ cần truy cập vào các vị trí liền kề để kiểm tra xem vị trí hiện tại có phải là duy nhất hay không.


1
2018-06-05 14:59





Cách tiếp cận của bạn có vẻ ổn. Có thể là anh đang tìm kiếm một trường hợp cạnh mà mảng có kích thước bằng nhau, có nghĩa là không có phần tử chưa từng có hoặc có hai hoặc nhiều hơn. Anh ta chỉ hỏi về nó một cách sai lầm.


0
2017-12-26 18:14