g***j
发帖数: 1275 | 1 请问，一般题目问kth smallest element的题目，是返回那个数字还是返回那个数字在
原来数组中的index？
这个题目肯定要打乱原来的数组的顺序吧？如果是要返回原来数组中的index，怎么办？ | m**a
发帖数: 139 | 2 放到一个{value,index}的struct里面然后再处理？ 比较大小只比较value。
办？
【在 g***j 的大作中提到】
: 请问，一般题目问kth smallest element的题目，是返回那个数字还是返回那个数字在
: 原来数组中的index？
: 这个题目肯定要打乱原来的数组的顺序吧？如果是要返回原来数组中的index，怎么办？
| g*********e
发帖数: 14401 | | p*i
发帖数: 411 | 4 #include
#include
#include
#include
using namespace std;
inline void swap(int &a, int &b) {
int t = a; a = b; b = t;
}
int partition(vector& work, vector& indices, int p, int q) {
// use work[q] to partition the array
const int x = work[q];
int i = p-1;
for (int j = p; j < q; j++) {
if (work[j] < x) {
i++;
swap(work[i], work[j]);
swap(indices[i], indices[j]);
}
}
i++;
swap(work[i], work[q]);
swap(indices[i], indices[q]);
return i;
}
int find_kthsmallest(const vector& A, int k) {
const int n = A.size();
assert((k >= 0) && (k < n));
int p = 0, q = n-1;
vector work(A), indices;
for (int i = 0; i < n; i++)
indices.push_back(i);
while (p < q) {
int r = partition(work, indices, p, q);
if (r-p == k) return indices[r];
else if (r-p < k) {
p = r+1;
k -= (r-p+1);
} else q = r-1;
}
return indices[p];
}
ostream& operator<<(ostream& os, const vector& A) {
for (int i = 0; i < A.size()-1; i++)
cout << A[i] << ' ';
cout << A[A.size()-1];
return os;
}
int main(int argc, char** argv) {
const int n = argc-2;
vector A;
for (int i = 2; i <= n+1; i++)
A.push_back(atoi(argv[i]));
const int k = atoi(argv[1]);
cout << A << endl;
cout << k << "th smallest element is: ";
int pos = find_kthsmallest(A, k-1);
cout << A[pos] << " at " << pos << endl;
return 0;
}
办？
【在 g***j 的大作中提到】
: 请问，一般题目问kth smallest element的题目，是返回那个数字还是返回那个数字在
: 原来数组中的index？
: 这个题目肯定要打乱原来的数组的顺序吧？如果是要返回原来数组中的index，怎么办？
| g***j
发帖数: 1275 | 5 请问你的程序里面第k小，是从多少开始的？ 第一个是k 为0还是k为1
这个partition返回的r是index吧？
如果k 的最小值为 1，就是最小的值
这句话不对吧？
int r = partition(work, indices, p, q);
if (r-p == k) return indices[r];
个人觉得应该是
if (r-p+1 == k) return indices[r];
【在 p*i 的大作中提到】
: #include
: #include
: #include
: #include
: using namespace std;
: inline void swap(int &a, int &b) {
: int t = a; a = b; b = t;
: }
: int partition(vector& work, vector& indices, int p, int q) {
: // use work[q] to partition the array
| p*i
发帖数: 411 | 6 main里面k从1开始，符合人的习惯
int pos = find_kthsmallest(A, k-1); <-- 我传了k-1
其它函数都是c++默认的从0开始，符合语言本身习惯
虽然这样没有必要。
【在 g***j 的大作中提到】
: 请问你的程序里面第k小，是从多少开始的？ 第一个是k 为0还是k为1
: 这个partition返回的r是index吧？
: 如果k 的最小值为 1，就是最小的值
: 这句话不对吧？
: int r = partition(work, indices, p, q);
: if (r-p == k) return indices[r];
: 个人觉得应该是
: if (r-p+1 == k) return indices[r];
| g***j
发帖数: 1275 | 7 哦，这样子。
【在 p*i 的大作中提到】
: main里面k从1开始，符合人的习惯
: int pos = find_kthsmallest(A, k-1); <-- 我传了k-1
: 其它函数都是c++默认的从0开始，符合语言本身习惯
: 虽然这样没有必要。
|
|
