Cho dãy số n số nguyên a[SUB]0[/SUB], a[SUB]1[/SUB],...a[SUB]n-1[/SUB]
hãy cho biết vị trí của k phần tử có giá trị lớn nhất của dãy?
AI BIET GIUP VOI .
hãy cho biết vị trí của k phần tử có giá trị lớn nhất của dãy?
AI BIET GIUP VOI .
có thể cho mh tham khảo cái Struct không bạn, cách của bạn đúng rồi
#include <algorithm>
#include <vector>
struct dataPos {
int val, pos;
dataPos() {} // có thể không cần dòng này.
dataPos(int v, int p) : val(v), pos(p) {}
bool operator<(const dataPos& another) const { return val > another.val; }
};
int main() {
vector<dataPos> a;
// đọc dữ liệu vào, với mỗi số x thứ i thì
// a.push_back(dataPos(x, i));
std::sort(a.begin(), a.end());
// in ra k giá trị từ dataPos[i].pos.
return 0;
}
int pos[MAX_N];
for (unsigned i = 0; i < n; ++i) pos[i] = i;
void quickSort(int a[], int left, int right) {
...
...
std::swap(a[i], a[j]);
std::swap(pos[i], pos[j]);
...
...
}
for (unsigned i = 0; i < k; ++i) printf("%d ", pos[i]);
Vì k chung chung ko biết lớn nhỏ, nên mình nghĩ đưa bài toán của bạn về dạng tìm rank của từng phần tử. Dễ nhất là bạn có thể tạo 1 mảng nữa lưu vị trí hiện tại của những phần tử này rồi sort lại:
1) Tạo 1 mảng với pos = i cho 0 <= i <= n - 1.
2) Sort lại mảng 'a' giảm/tăng dần, tuy nhiên lúc đổi chỗ thì phải đổi luôn 2 phần tử của 'pos'. Ví dụ:
swap(a, a[j]);
swap(pos, pos[j]);
3) Lấy k phần tử ở đầu/cuối của dãy 'pos' tùy theo cách bạn sort. Ví dụ khi sort giảm dần thì nếu pos[0] = x1 thì a[x1] là phần tử lớn nhất của dãy ban đầu, nếu pos[1] = x2 thì a[x2] là phần tử lớn nhì của dãy ban đầu,...
Độ phức tạp của thuật toán O(n log n), dùng quick sort cho dễ.
Nếu bạn học Struct rồi thì có thể dùng built-in 'sort' của C++ sẽ nhanh hơn tự viết (và ngắn hơn nữa).
Bởi vì chủ topic không nói rõ giá trị của n và k nên mình phải assume rằng nó lớn. Vì vậy, những thuật toán sort có complexity là O(n^2) đều bị bỏ qua cả. Nếu k nhỏ thì bài này chỉ cần chạy k lần, mỗi lần tìm số max là đc, ko cần phải sort để cho phức tạp. Nhưng nếu n = k = 10000 thì sẽ thấy sự chênh lệch rất lớn.thớt xài quicksort thì nghe có vẻ phức tạp hơn là phải, theo em nếu học cơ bản thớt nên chỉ bubblesort trước, em góp ý tí thôi nha thớt
p/s: code quick sort có sẵn trong pascal chỉ cần copy paste vào thôi
C:\FPC\3.0.0\demo\text\qsort.pp
if (a[i] < a[j]) {
swap(a[i], a[j]);
swap(pos[i], pos[j]);
}
void quickSort(int a[], int left, int right) {
if (left >= right) return;
int pivot = a[rand() % (right - left + 1) + left];
int i = left, j = right;
do {
while (a[i] > pivot) ++i;
while (a[j] < pivot) --j;
if (i <= j) {
if (i < j) {
std::swap(a[i], a[j]);
std::swap(pos[i], pos[j]);
}
++i; --j;
}
} while (i <= j);
quickSort(a, left, j);
quickSort(a, i, right);
}
srand(time(0));
quickSort(a, 0, n - 1);
#include <time.h>
#include <stdlib.h>
#include <algorithm>
// Đầu tiên random ra MAXN số, mỗi số trong khoảng [0, MAXE). Để cho dễ chỉ lấy MAXN = 10.
// Khi random thì in ra mảng a ban đầu luôn.
srand(time(0));
for (int i = 0; i < MAXN; ++i) {
a[i] = rand() % MAXE;
pos[i] = i;
printf("%d ", a[i]);
}
printf("\n");
quickSort(a, 0, MAXN - 1); // sort lại theo giảm dần.
// In ra mảng a đã sort.
for (int i = 0; i < MAXN; ++i) printf("%d ", a[i]);
printf("\n");
// In ra vị trí của K phần tử lớn nhất của mảng.
// Đối chiếu với mảng a ngay trên, bạn xem ban đầu nó có phải ở vị trí đó hay không.
for (int i = 0; i < K; ++i) printf("%d ", pos[i]);