Tùy thuộc vào các thông số của sự cố của bạn, có nhiều cách để giải quyết vấn đề này.
Nếu bạn không được phép sử dụng bộ nhớ ngoài O (n), thì một tùy chọn sẽ sử dụng thuật toán phân loại chuẩn để sắp xếp mảng tại chỗ trong thời gian O (n log n), sau đó chạy một lần thứ hai vượt qua nó để di chuyển các bản sao đến cuối (như bạn đã đề xuất). Mã bạn đăng ở trên mất thời gian O (n), nhưng tôi nghĩ rằng bước này có thể được thực hiện trong thời gian O (n log n) bằng cách sử dụng thuật toán phức tạp hơn một chút. Ý tưởng này hoạt động theo hai bước. Trong bước đầu tiên, trong thời gian O (n log n) bạn đưa tất cả các phần tử không trùng lặp lên phía trước theo thứ tự sắp xếp và mang tất cả các bản sao vào mặt sau theo thứ tự không được sắp xếp. Một khi bạn đã làm điều đó, sau đó bạn sắp xếp nửa sau của mảng trong thời gian O (n log n) bằng cách sử dụng thuật toán sắp xếp từ bước đầu tiên.
Tôi sẽ không đi vào mã để sắp xếp mảng. Tôi thực sự thích phân loại, nhưng có rất nhiều tài nguyên tốt khác về cách sắp xếp mảng tại chỗ mà nó không phải là một sử dụng tốt thời gian/không gian của tôi ở đây để đi vào chúng.Nếu nó giúp, thì đây là các liên kết đến việc triển khai Java của heapsort, quicksort và smoothsort, tất cả đều chạy trong thời gian O (n log n). Heapsort và smoothsort chỉ sử dụng O (1) bộ nhớ ngoài, trong khi quicksort có thể sử dụng O (n) trong trường hợp xấu nhất (mặc dù việc triển khai tốt có thể hạn chế điều này thành O (log n) sử dụng các thủ thuật dễ thương).
Mã thú vị là logic để đưa tất cả các phần tử không trùng lặp vào trước phạm vi. Trực giác, mã hoạt động bằng cách lưu trữ hai con trỏ - một con trỏ đã đọc và một con trỏ ghi. Con trỏ đọc trỏ tới phần tử tiếp theo để đọc, trong khi con trỏ ghi trỏ đến vị trí đặt phần tử duy nhất tiếp theo. Ví dụ, cho mảng này:
1 1 1 1 2 2 3 4 5 5
Chúng tôi bắt đầu với đọc và viết gợi ý ban đầu chỉ ở mức 1:
write v
1 1 1 1 2 2 3 4 5 5
read ^
Tiếp theo, chúng ta hãy bỏ qua con trỏ đọc trước để các yếu tố tiếp theo mà không phải là 1. Đây thấy 2:
write v
1 1 1 1 2 2 3 4 5 5
read ^
sau đó, chúng tôi bump con trỏ ghi vào vị trí tiếp theo:
write v
1 1 1 1 2 2 3 4 5 5
read ^
Bây giờ, chúng tôi trao đổi 2 vào vị trí tổ chức bởi con trỏ ghi:
write v
1 2 1 1 1 2 3 4 5 5
read ^
trước con trỏ đọc với giá trị tiếp theo mà không phải là 2:
write v
1 2 1 1 1 2 3 4 5 5
read ^
sau đó thúc đẩy viết con trỏ:
write v
1 2 1 1 1 2 3 4 5 5
read ^
Một lần nữa, chúng tôi trao đổi các giá trị được chỉ bằng 'đọc' và 'viết' và di chuyển con trỏ viết về phía trước, sau đó m Ove con trỏ đọc với giá trị độc đáo tiếp theo:
write v
1 2 3 1 1 2 1 4 5 5
read ^
Một lần nữa sản lượng
write v
1 2 3 4 1 2 1 1 5 5
read ^
và lặp thức cho
write v
1 2 3 4 5 2 1 1 1 5
read ^
Nếu bây giờ chúng ta loại từ con trỏ ghi vào đọc con trỏ, chúng tôi nhận được
write v
1 2 3 4 5 1 1 1 2 5
read ^
và bingo! Chúng tôi có câu trả lời mà chúng tôi đang tìm kiếm.
In (chưa được kiểm tra, xin lỗi ...) mã Java, bước fixup này có thể trông như thế này:
int read = 0;
int write = 0;
while (read < array.length) {
/* Swap the values pointed at by read and write. */
int temp = array[write];
array[write] = array[read];
array[read] = temp;
/* Advance the read pointer forward to the next unique value. Since we
* moved the unique value to the write location, we compare values
* against array[write] instead of array[read].
*/
while (read < array.length && array[write] == array[read])
++ read;
/* Advance the write pointer. */
++ write;
}
thuật toán này chạy trong thời gian O (n) thời gian, dẫn đến một O tổng thể (n log n) thuật toán cho vấn đề. Vì bước sắp xếp lại sử dụng bộ nhớ O (1), việc sử dụng bộ nhớ tổng thể sẽ là O (1) (đối với một cái gì đó như smoothsort hoặc heapsort) hoặc O (log n) (cho một cái gì đó như quicksort).
EDIT: Sau khi nói chuyện này với một người bạn, tôi nghĩ rằng có một giải pháp thanh lịch hơn cho vấn đề dựa trên sửa đổi quicksort.Thông thường, khi bạn chạy quicksort, bạn sẽ kết thúc phân vùng mảng thành ba vùng:
+----------------+----------------+----------------+
| values < pivot | values = pivot | values > pivot |
+----------------+----------------+----------------+
Việc đệ quy sẽ sắp xếp các vùng đầu tiên và cuối cùng để đưa chúng vào thứ tự sắp xếp. Tuy nhiên, chúng tôi có thể sửa đổi điều này cho phiên bản của sự cố. Chúng ta cần một thuật toán nguyên thủy là xoay, lấy hai khối giá trị liền kề trong một mảng và trao đổi chúng trong thời gian O (n). Nó không thay đổi thứ tự tương đối của các phần tử trong các khối đó. Ví dụ, chúng ta có thể sử dụng luân phiên để chuyển đổi các mảng
1 2 3 4 5 6 7 8
vào
3 4 5 6 7 8 1 2
và có thể làm như vậy trong thời gian O (n) thời gian.
Phiên bản sửa đổi của quicksort sẽ hoạt động bằng cách sử dụng phân vùng ba chiều Bentley-McIlroy algortihm (được mô tả here) đến, sử dụng không gian thêm (O), sắp xếp lại các phần tử mảng vào cấu hình được hiển thị ở trên. Tiếp theo, chúng tôi áp dụng luân phiên để sắp xếp lại các yếu tố để họ trông như thế này:
+----------------+----------------+----------------+
| values < pivot | values > pivot | values = pivot |
+----------------+----------------+----------------+
Tiếp theo, chúng ta thực hiện một trao đổi để chúng ta di chuyển chính xác một bản sao của phần tử trục vào tập các phần tử ít nhất là lớn làm trục xoay. Điều này có thể có thêm các bản sao của trục sau. Chúng tôi sau đó đệ quy áp dụng thuật toán sắp xếp cho các phạm vi < và>. Khi chúng tôi thực hiện việc này, mảng kết quả sẽ trông giống như sau:
+---------+-------------+---------+-------------+---------+
| < pivot | dup < pivot | > pivot | dup > pivot | = pivot |
+---------+-------------+---------+-------------+---------+
Sau đó, chúng tôi áp dụng hai phép quay cho phạm vi để đưa nó vào thứ tự cuối cùng. Đầu tiên, xoay các giá trị trùng lặp nhỏ hơn trục xoay với các giá trị lớn hơn trục xoay. Điều này cho phép
+---------+---------+-------------+-------------+---------+
| < pivot | > pivot | dup < pivot | dup > pivot | = pivot |
+---------+---------+-------------+-------------+---------+
Tại thời điểm này, phạm vi đầu tiên này là yếu tố duy nhất trong thứ tự tăng dần:
+---------------------+-------------+-------------+---------+
| sorted unique elems | dup < pivot | dup > pivot | = pivot |
+---------------------+-------------+-------------+---------+
Cuối cùng, thực hiện một vòng quay cuối cùng của các yếu tố trùng lặp lớn hơn trục và các yếu tố tương đương với trục để nhường này:
+---------------------+-------------+---------+-------------+
| sorted unique elems | dup < pivot | = pivot | dup > pivot |
+---------------------+-------------+---------+-------------+
Chú ý rằng ba khối cuối cùng chỉ là những giá trị nhân bản được sắp xếp:
+---------------------+-------------------------------------+
| sorted unique elems | sorted duplicate elements |
+---------------------+-------------------------------------+
và thì đấy! Chúng tôi có mọi thứ theo thứ tự mà chúng tôi muốn. Sử dụng cùng một phân tích mà bạn muốn làm cho quicksort bình thường, cộng với thực tế rằng chúng tôi chỉ làm O (n) làm việc ở mỗi cấp (ba phép quay thêm), điều này làm việc với O (n log n) trong trường hợp tốt nhất với việc sử dụng bộ nhớ O (log n). Nó vẫn là O (n) trong trường hợp xấu nhất với bộ nhớ O (log n), nhưng điều đó xảy ra với xác suất cực thấp.
Nếu bạn được phép sử dụng bộ nhớ O (n), một tùy chọn sẽ xây dựng cây tìm kiếm nhị phân cân bằng trong tất cả các phần tử lưu trữ cặp khóa/giá trị, trong đó mỗi khóa là một phần tử của mảng và giá trị là số lần nó xuất hiện.Sau đó bạn có thể sắp xếp mảng trong định dạng của bạn như sau:
- Đối với mỗi phần tử trong mảng:
- Nếu yếu tố đó đã tồn tại trong BST, tăng số lượng của nó.
- Nếu không, thêm một nút mới vào BST với nguyên tố có số 1.
- Do một đi bộ inorder của BST. Khi gặp phải một nút, hãy xuất khóa của nó.
- Thực hiện bước đi bộ thứ hai của BST. Khi gặp phải một nút, nếu nó có số lượng lớn hơn một, thì xuất ra n - 1 bản sao của nút đó, trong đó n là số lần nó xuất hiện.
Thời gian chạy của thuật toán này là O (n log n), nhưng sẽ rất khó để mã hóa BST từ đầu. Nó cũng yêu cầu không gian bên ngoài, mà tôi không chắc chắn bạn được phép làm.
Tuy nhiên, nếu bạn được phép sử dụng không gian bên ngoài và các mảng bạn sắp xếp nhỏ và chứa số nguyên nhỏ, bạn có thể sửa đổi cách tiếp cận trên bằng cách sử dụng sửa đổi counting sort. Chỉ cần thay thế BST bằng một mảng đủ lớn cho mỗi số nguyên trong mảng ban đầu là một khóa. Điều này làm giảm thời gian chạy thành O (n + k), với việc sử dụng bộ nhớ O (k), trong đó k là phần tử lớn nhất trong mảng.
Hy vọng điều này sẽ hữu ích!
Sắp xếp bong bóng? Có thật không? –
@Nick Johnson: Hãy nhớ rằng, anh ấy đang học lập trình. –
Sau đó, vấn đề của tôi là với bất cứ ai dạy anh ta - dạy bong bóng loại như bất cứ điều gì khác hơn là một ví dụ về "thuật toán ngây thơ mà không, trên thực tế, làm việc rất tốt" là vô trách nhiệm. :) –