Trung tâm cá nhân
cuốn sách gpt4 ai đã làm

Thuật toán - Sắp xếp danh sách hậu tố

In lại Tác giả: Taklimakan Thời gian cập nhật: 2023-11-03 02:53:01 27 4
mua khóa gpt4 Nike

Đối với các phần tử trong mảng/danh sáchxViệc sắp xếp được thực hiện chỉ để tìm ra có bao nhiêu phần tử trong mảng/danh sách nhỏ hơn x.
Vì vậy, xếp hạng một danh sách là xếp hạng tất cả các phần tử trong danh sách.
例如，hạng [51, 38, 29, 51, 63, 38] = [3, 1, 0, 3, 5, 1], tức là có 3 phần tử nhỏ hơn 51, v.v.
Việc sắp xếp danh sách có thể được thực hiện trong O(nlogn). Về cơ bản, chúng ta có thể sắp xếp danh sách trong khi ghi nhớ chỉ mục gốc của từng phần tử, sau đó xem số lượng chỉ mục trước mỗi phần tử.
Câu hỏi ở đây là làm thế nào đểO(NlogN)hậu tố trong danh sách được sắp xếp?
Sắp xếp danh sách theo hậu tố có nghĩa là:
Đối với danh sách [3;1;2], xếp hạng [[3;1;2];[1;2];[2]]
Lưu ý rằng các yếu tố có thể không rõ ràng.
biên tập
Chúng ta không cần in ra tất cả các phần tử có đủ hậu tố. Bạn có thể tưởng tượng rằng chúng ta chỉ cần in ra một danh sách/mảng trong đó mỗi phần tử là một nhóm cột có hậu tố.
Ví dụ: Rank suffix_u of_3;1;2]=rank[[3;1;2];[1;2];[2]]=[2;0;1] thì bạn chỉ cần in ra [2;0; 1].
编辑2
Hãy để tôi giải thích rõ hơn ở đây tất cả các hậu tố là gì và sắp xếp/sắp xếp tất cả các hậu tố là gì.
Giả sử chúng ta có một mảng/danh sách [e1;e2;e3;e4;e5].
Khi đó tất cả các hậu tố của [e1; e2; e4; e5] là:
[E1;E2;E3;E4;E5]
[E2;E3;E4;E5]
[E3;E4;E5]
[E4;E5]
[E5]
Ví dụ: tất cả các hậu tố của [4;2;3;1;0] đều là
[4;2;3;1;0]
[2;3;1;0]
[3;1;0]
[1;0]
[0]
Sắp xếp với hơn 5 hậu tố có nghĩa là phân loại từ điển. Sắp xếp tất cả các hậu tố bạn sẽ nhận được
[0]
[1;0]
[2;3;1;0]
[3;1;0]
[4;2;3;1;0]
Nhân tiện, nếu bạn không thể tưởng tượng được 5 danh sách/mảng có thể được sắp xếp giữa chúng, thì hãy nghĩ đến việc sắp xếp các chuỗi theo từ điển.
"0"<"10"<"2310"<"310"<"42310"
Có vẻ như việc sắp xếp tất cả các hậu tố thực sự sắp xếp tất cả các phần tử của mảng ban đầu.
Tuy nhiên, xin lưu ý rằng tất cả các phần tử có thể không hoàn toàn khác nhau, ví dụ:
Đối với [4;2;2;1;0], tất cả các hậu tố là:
[4;2;2;1;0]
[2;2;1;0]
[2;1;0]
[1;0]
[0]
Sau đó, thứ tự là
[0]
[1;0]
[2;1;0]
[2;2;1;0]
[4;2;2;1;0]

câu trả lời hay nhất

Như mbo đã chỉ ra một cách chính xác, câu hỏi của bạn là về việc xây dựng danh sách đầu vàomảng hậu tố. Để làm điều này, thuật toán nhanh và phức tạp thực sự là thời gian tuyến tính, nhưng vì bạn chỉ nhắm mục tiêuO(n log n), Tôi sẽ cố gắng đưa ra một phiên bản đơn giản hơn, dễ thực hiện hơn.
Ý tưởng cơ bản và triển khai ban đầu
theo trình tựO(n log2 n)Ví dụ. Hậu tố của nó là

0: 4 2 2 1
1: 2 2 1
2: 2 1
3:1

Tôi đánh số các hậu tố theo thứ tự ban đầu bằng cách sử dụng chỉ mục bắt đầu của chúng. Cuối cùng, chúng tôi muốn nhanh chóng sắp xếp bộ hậu tố này. Chúng tôi biết rằng chúng tôi có thể biểu thị từng hậu tố trong không gian không đổi bằng cách sử dụng chỉ mục bắt đầu của nó và chúng tôi có thể sử dụng sắp xếp hợp nhất, sắp xếp theo đống hoặc các thuật toán tương tự để [4, 2, 2, 1]Sắp xếp theo so sánh. Vì vậy, câu hỏi vẫn là làm thế nào để chúng ta so sánh nhanh chóng hai hậu tố?
Giả sử chúng ta muốn so sánh các hậu tố O(n log n)Và [2, 2, 1]. Chúng ta có thể điền những giá trị làm thay đổi kết quả so sánh bằng các giá trị vô cực âm: [hai mươi mốt]Và [2, 2, 1, -∞].
Ý tưởng chính ở đây là quan sát phân chia và chinh phục sau đây: thay vì so sánh từng ký tự cho đến khi tìm thấy hai vị trí khác nhau, chúng ta có thể chia hai danh sách làm đôi và so sánh hai nửa của từ điển: 
     [a, b, c, d] < [e, f, g, h] 
 <=> ([a, b], [c, d]) < ([e, f], [g, h])
 <=> [a, b] < [e, f] hoặc ([a, b,] = [e, f] và [c, d] < [g, h])

Về cơ bản, chúng ta chia bài toán so sánh trình tự thành hai bài toán so sánh trình tự nhỏ hơn. Điều này dẫn đến thuật toán sau:
Bước 1: Sắp xếp các chuỗi con (chuỗi con liền kề) có độ dài 1. Trong ví dụ của chúng tôi, chuỗi con có độ dài 1 là [2, 1, -∞, -∞]. Mỗi chuỗi con có thể được biểu thị bằng vị trí bắt đầu của nó trong danh sách ban đầu. Chúng tôi sắp xếp chúng bằng cách sắp xếp so sánh đơn giản và nhận được [4], [2], [2], [1]. Chúng ta lưu trữ kết quả bằng cách gán chúng vào từng vị trí trong danh sách đã sắp xếp: 
thứ hạng chuỗi con vị trí
0 [4] 2
1 [2] 1
2 [2] 1
3 [1] 0

Điều quan trọng là chúng ta gán các cấp bậc bằng nhau cho các chuỗi con bằng nhau!
Bước 2: Bây giờ chúng ta muốn sắp xếp chuỗi con có độ dài 2. Thực tế chỉ có 3 chuỗi con như vậy, nhưng nếu cần, chúng tôi phân bổ một chuỗi con cho mỗi vị trí bằng cách đệm thêm âm vô cực. Mẹo ở đây là chúng ta có thể so sánh nhanh bằng cách sử dụng ý tưởng "chia để trị" ở trên và các nhóm cột được chỉ định ở bước 1 (điều này chưa thực sự cần thiết nhưng sẽ trở nên quan trọng sau này). 
vị trí chuỗi con một nửa xếp hạng từ bước 1 xếp hạng cuối cùng
0 [4, 2] ([4], [2]) (2, 1) 3               
1 [2, 2] ([2], [2]) (1, 1) 2
2 [2, 1] ([2], [2]) (1, 0) 1
3 [1, -∞] ([1], [-∞]) (0, -∞) 0

Bước 3: Bạn đoán đúng rồi, bây giờ chúng ta sắp xếp chuỗi con có độ dài 4(!). . Đây chính xác là những hậu tố cho danh sách! Lần này chúng ta có thể sử dụng kỹ thuật "chia để trị" và kết quả từ bước 2: 
vị trí một nửa chuỗi con xếp hạng từ bước 2 xếp hạng cuối cùng
0 [4, 2, 2, 1] ([4, 2], [2, 1]) (3, 1) 3
1 [2, 2, 1, -∞] ([2, 2], [1, -∞]) (2, 0) 2
2 [2, 1, -∞, -∞] ([2, 1], [-∞,-∞]) (1, -∞) 1
3 [1, -∞, -∞, -∞] ([1,-∞], [-∞,-∞]) (0, -∞) 0

Chúng ta chết tiệt! Nếu kích thước của chuỗi ban đầu của chúng tôi là [1], [2], [2], [4], chúng tôi cần 2^kbước chân. Hoặc ngược lại, chúng ta cần kCác bước xử lý kích thước log_2 nsự liên tiếp. Nếu độ dài của nó không phải là lũy thừa của hai, chúng ta sẽ thêm vào nó một âm vô cực.
Để triển khai thực tế, chúng ta chỉ cần nhớ “xếp hạng cuối cùng” tuần tự của từng bước của thuật toán.
Việc triển khai trong C++ có thể giống như thế này (sử dụng nđã biên soạn): 
#include 
#include 
using namespace std;

int seq[] = {8, 3, 2, 4, 2, 2, 1};
const int n = 7;
const int log2n = 3 // log2n = ceil(log_2(n))
int Rank[log2n + 1][n]; // Rank[i] sẽ lưu lại Rank cuối cùng của bước i
tuple L[n]; // L là danh sách các bộ dữ liệu ở bước i,
                           // cái này sẽ giữ các cặp Xếp hạng từ bước i - 1
                           // cùng với chỉ mục chuỗi con
const int neginf = -1; // phải nhỏ hơn tất cả các số trong seq
int chính() {
  vì (int i = 0; i < n; ++i)
    Rank[1][i] = seq[i]; // bước 1 thực sự đơn giản nếu bạn nghĩ về nó
  for (int step = 2; step <= log2n; ++step) {
    int length = 1 << (bước - 1); // độ dài là 2^(bước - 1)
    vì (int i = 0; i < n; ++i)
      L[i] = make_tuple(
                Xếp hạng[bước - 1][i],
                (i + chiều dài / 2 < n) ? Xếp hạng[bước - 1] [i + chiều dài / 2] : phủ định,
                i); // sau này chúng ta cần biết tuple đến từ đâu
    Sort(L, L + n); // sắp xếp theo từ điển
    vì (int i = 0; i < n; ++i) {
      // chúng ta lưu thứ hạng của chỉ mục, nhưng chúng ta cần cẩn thận
      // gán thứ hạng bằng nhau cho các cặp bằng nhau
      Xếp hạng[bước][get<2>(L[i])] = (i > 0 && get<0>(L[i]) == get<0>(L[i - 1])
                                        && get<1>(L[i]) == get<1>(L[i - 1]))
                                    ? Xếp hạng[bước][get<2>(L[i - 1])] 
                                    :Tôi;
    }
  }
  // mảng hậu tố nằm trong L sau bước cuối cùng
  vì (int i = 0; i < n; ++i) {
    int bắt đầu = get<2>(L[i]);
    cout << bắt đầu << ://;
    cho (int j = bắt đầu; j < n; ++j)
      cout << " " << seq[j];
    cout << endl;
  }
}

Đầu ra: 
6:1
5: 2 1
4: 2 2 1
2: 2 4 2 2 1
1: 3 2 4 2 2 1
3: 4 2 2 1
0: 8 3 2 4 2 2 1

Sự phức tạp là -std=c++11, trong việc thực hiện này nó là O(log n * (n + sắp xếp)), bởi vì chúng tôi sử dụng các kiểu so sánh phức tạp O(n log2 n)
một sự đơn giản O(n log n)thuật toán
Nếu chúng ta có thể thực hiện được ở mỗi bước O(n log n)Trong phần sắp xếp, bạn sẽ nhận được TRÊN)ranh giới. Vì vậy, về cơ bản chúng ta cần sắp xếp một loạt các cặp. Chúng tôi biết chúng tôi có thể sử dụng sắp xếp đếmhiện hữu O(n log n)Sắp xếp một chuỗi các số nguyên trong một phạm vi thời gian nhất định. Chúng ta có thể đặt (x, y)dưới dạng số trong cơ số n 0 <= x, y < nMã hóa. Bây giờ chúng ta có thể thấy cách sử dụng Sắp xếp cơ số LSDSắp xếp các cặp này.
Trong thực tế, điều này có nghĩa là bằng cách sử dụng cách sắp xếp đếm chúng ta sẽ tăng TRÊN)để sắp xếp các cặp, sau đó lại sử dụng cách sắp xếp đếm để tăng (x, y)để sắp xếp. Vì việc sắp xếp đếm ổn định nên chúng tôi đưa ra thứ tự các cặp của mình. Sự phức tạp cuối cùng là thế này.
Nếu quan tâm, bạn có thể tìm hiểu cách z = n * x + y实现 tại kho lưu trữ Github của tôi. Việc thực hiện có 27 dòng mã. Khá tốt phải không?

Về thuật toán - hậu tố cho danh sách hoán vị, chúng tôi tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/21220150/

27 4 0
Bài viết khuyến nghị: Cách hiệu quả nhất để sắp xếp danh sách các số thành một chuỗi thấp-cao-thấp xen kẽ là gì?
Bài viết khuyến nghị: Sự khác biệt giữa chiều dài và chiều dài() là gì?
Bài viết khuyến nghị: Đọc tệp CSV trong java thêm khoảng trắng giữa mỗi ký tự
Bài viết khuyến nghị: Đặt mức trung bình O(1) và mức tối đa/phút tệ nhất O(log n) để thêm/xóa
Taklimakan
Hồ sơ

Tôi là một lập trình viên xuất sắc, rất giỏi!

Nhận phiếu giảm giá taxi Didi miễn phí
Phiếu giảm giá taxi Didi
Các bài viết phổ biến trên toàn bộ trang web
Chứng chỉ ICP Bắc Kinh số 000000
Hợp tác quảng cáo: 1813099741@qq.com 6ren.com
Xem sitemap của VNExpress