Lower_bound và upper_bound là các hàm tìm kiếm nhị phân được tích hợp sẵn.
Lower_bound - một hàm, theo thời gian logarit, tìm phần tử nhỏ nhất trong một mảng đã sắp xếp lớn hơn hoặc bằng giá trị k đã cho.
Nó lấy giới hạn của mảng và giá trị của k làm đối số.
Trả về một trình vòng lặp cho phần tử tìm thấy hoặc đến phần cuối (không bao gồm) của mảng nếu không có phần tử nào như vậy tồn tại.
Bạn có thể đọc thêm trong tài liệu.
upper_bound - một hàm theo thời gian logarit trong một mảng đã sắp xếp sẽ tìm phần tử nhỏ nhất lớn hơn giá trị k đã cho.
Nó lấy giới hạn của mảng và giá trị của k làm đối số.
Trả về một trình vòng lặp cho phần tử tìm thấy hoặc đến phần cuối (không bao gồm) của mảng nếu không có phần tử nào như vậy tồn tại.
Bạn có thể đọc thêm trong tài liệu.
Cần làm rõ rằng việc sử dụng các hàm này trên một tập hợp hoặc nhiều tập hợp không hoạt động trong thời gian logarit do thiếu bộ lặp trong các tập hợp truy cập ngẫu nhiên ở trên.
Tuy nhiên, các bộ sưu tập này có các phương thức tích hợp sẵn tương ứng (nghĩa là bạn cần sử dụng chúng "thông qua dấu chấm").
Ví dụ:
vectơ a = { 0, 1, 3, 5, 7 };
vector::iterator it;
nó = Lower_bound(a.begin(), a.end(), 4);
// * nó == 5
nó = Lower_bound(a.begin(), a.end(), 5);
// * nó == 5
nó = Lower_bound(a.begin(), a.end(), 8);
// nó == a.end()
it = upper_bound(a.begin(), a.end(), 4);
// * nó == 5
it = upper_bound(a.begin(), a.end(), 5);
// * nó == 7
it = upper_bound(a.begin(), a.end(), -1);
// * nó == 0
// bằng cách trừ đi các vòng lặp, bạn có thể lấy chỉ mục của phần tử được tìm thấy
int ind = Lower_bound(a.begin(), a.end(), 4) - a.begin();
// ind == 3
// cần sử dụng các phương thức thay vì các hàm cho tập hợp và các tập hợp tương tự
tập hợp s{ 1, 3, 5 };
set::iterator ngồi;
ngồi = s.lower_bound(3);
// *ngồi == 3
ngồi = s.upper_bound(3);
// *ngồi == 5
|
duy nhất - một chức năng nén tất cả các chuỗi phần tử liên tiếp giống hệt nhau thành một trong thời gian tuyến tính.
Là một đối số, nó được chuyển qua các ranh giới của mảng, trong đó cần áp dụng nén.
Một trình vòng lặp được trả về phần cuối mới (không bao gồm) của mảng. Bạn nên cẩn thận với các phần tử sau phần cuối mới nhưng trước phần cuối cũ, vì chúng sẽ có giá trị không xác định.
Bạn có thể đọc thêm trong tài liệu.
Nếu bạn đang sử dụng chức năng này trên một véc-tơ, thì việc thay đổi kích thước bằng cách sử dụng kết quả trả về sẽ rất tiện lợi (thêm về điều đó bên dưới).
Ví dụ:
véc tơ a = { 3, 3, 3, 2, 3, 3, 1, 1, 4, 5, 5 };
duy nhất (a.begin(), a.end());
// a = [3, 2, 3, 1, 4, 5, ?, ?, ?, ?, ?]
// sử dụng chức năng duy nhất là thuận tiện để làm
// mảng phụ để nén tọa độ
a = { 235, 10, 41, 10, 41, 41, 235, 500, 500 };
sắp xếp(a.begin(), a.end());
// a = [10, 10, 41, 41, 41, 235, 235, 500, 500]
a.resize(duy nhất(a.begin(), a.end()) - a.begin());
// a = [10, 41, 235, 500]
|
hợp nhất - một hàm hợp nhất hai mảng đã sắp xếp, cụ thể là trong thời gian tuyến tính, nó nhận được một mảng đã sắp xếp, bao gồm các phần tử của mảng thứ nhất và thứ hai.
Nó nhận 5 đối số: hai giới hạn cho mỗi mảng và giới hạn bên trái của đích (nơi các phần tử của mảng kết quả sẽ được đặt).
Bạn có thể tìm thêm chi tiết trong tài liệu.
Ví dụ:
// mảng nguồn phải được sắp xếp
vectơ a = { 1, 3, 5, 7 };
vectơ b = {2, 4, 6};
// cần đích đủ lớn
vecto c(7);
hợp nhất (a.begin(), a.end(), b.begin(), b.end(), c.begin());
// c = [1, 2, 3, 4, 5, 6, 7]
// các phần tử có thể được lặp lại
a = {1, 2, 4, 4};
b = { 2, 3, 3, 3, 4, 4 };
c.resize(10);
hợp nhất (a.begin(), a.end(), b.begin(), b.end(), c.begin());
// c = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
Hàm này rất hữu ích trong bối cảnh sắp xếp hợp nhất.
|
nth_element là hàm cho phép bạn tìm phần tử thứ n trong mảng theo thứ tự đã sắp xếp theo thời gian tuyến tính.
Hàm lấy phần cuối bên trái của mảng, một trình vòng lặp đến vị trí có giá trị theo thứ tự được sắp xếp sẽ được tìm thấy và phần cuối bên phải của mảng.
Sau khi áp dụng hàm, giá trị cần thiết sẽ được đặt tại vị trí được chỉ định bởi trình vòng lặp, trong khi các giá trị còn lại sẽ có thứ tự hỗn loạn, nhưng ở bên trái của thứ n sẽ có các giá trị không nhiều hơn nó và bên phải không ít. Nghĩa là, nên hiểu rằng hàm này phá bỏ thứ tự ban đầu của các phần tử.
Bạn có thể đọc thêm trong tài liệu (https://www.cplusplus.com/reference/algorithm/nth_element/).
Ví dụ:
vectơ a = { 4, 0, 3, 9, 2, 1, 8, 5, 6, 7 };
// tìm phần tử ở chỉ số 4
// chú ý đến thứ tự của các đối số
nth_element(a.begin(), a.begin() + 4, a.end());
// a = [#, #, #, #, 4, $, $, $, $, $]
// trong đó # <= 4 và 4 <= $
|
Một hoán vị có độ dài n là một tập hợp có thứ tự không lặp lại các số 1, 2, ..., n. Ví dụ: [3, 1, 2] và [5, 4, 3, 2, 1] là hoán vị, nhưng [1, 2, 1, 3] và [1, 2, 4] thì không.
Nếu nhiệm vụ được rút gọn thành thực tế là cần phải lặp lại tất cả các hoán vị có độ dài n, thì bạn có thể sử dụng một cơ chế thuận tiện trong C ++, được gọi là "next_permutation".
Bạn có thể đọc thêm về nó trong tài liệu, nhưng điểm mấu chốt là hàm này thay đổi mảng đã truyền đến hoán vị tiếp theo theo thứ tự từ điển (thường rõ ràng và tên của nó).
Để sử dụng next_permutation, bạn cần đưa vào thư viện thuật toán (nghĩa là viết #include <algorithm> ở đầu chương trình)
Ví dụ:
véc tơ mảng;
mảng = { 1, 2, 3 }; // mảng là [1, 2, 3]
next_permutation(arr.begin(), arr.end()); // truyền toàn bộ mảng cho hàm
// mảng bây giờ là [1, 3, 2]
mảng = {2, 3, 1}; // mảng là [2, 3, 1]
next_permutation(arr.begin(), arr.end()); // truyền toàn bộ mảng cho hàm
// mảng bây giờ là [3, 1, 2]
next_permutation(mảng.bắt đầu() + 1, mảng.bắt đầu() + 3); // có thể áp dụng một hàm cho một phần của mảng, nhưng trong thực tế điều này hiếm khi cần thiết
// mảng bây giờ là [3, 2, 1]
Trong trường hợp này, hàm có giá trị trả về kiểu boolean là true nếu hoán vị tiếp theo được tạo và sai nếu không có hoán vị tiếp theo (trường hợp khi hoán vị tối đa theo thứ tự từ điển được truyền cho hàm).
Điều này cho phép sử dụng hàm trong một vòng lặp, điều này sẽ cho phép chúng ta lặp lại tất cả các hoán vị cùng một lúc. Do lập chỉ mục 0, trong thực tế, việc hoán vị các số từ 0 đến n - 1 thường thuận tiện hơn, mặc dù hoán vị chính thức chứa các số từ 1 đến n. Nhưng may mắn thay, điều này không dẫn đến các lớp phủ bổ sung trong mã, bởi vì hàm next_permutation được điều chỉnh theo các hoán vị có chỉ số 0 (và thậm chí cả các phần tử trùng lặp trong một mảng, nhưng bạn có thể tự mình tìm hiểu thêm).
Nói chung, mã để lặp qua tất cả các hoán vị trông giống như sau:
intn; // kích thước hoán vị
vectorperm(n); // perm là viết tắt của "hoán vị", tức là "hoán vị"
for (int i = 0; i < n; i++)
perm[i] = i; // khởi tạo hoán vị ban đầu 0, 1, ..., n - 1
LÀM {
// bên trong vòng lặp, chúng tôi xử lý hoán vị hiện tại
} while (next_permutation(perm.begin(), perm.end())); // nếu không có hoán vị tiếp theo thì kết thúc vòng lặp
Mã này chạy trong O(n! * f(n)), trong đó f(n) là thời gian bạn cần để xử lý một hoán vị cụ thể.
|