d*******u
发帖数: 90 | 1 Can anyone provide an efficient C code for the following probem, minimizing
the calculating time.
20 random numbers, 10 of them are even, the other 10 are odd.
order the 20 numbers in an alternate way in terms of odd and even.
Also, all the even numbers should be in an decreasing way. same for odd
numbers.
Thanks | d******s
发帖数: 274 | 2 extra space:
traverse and separate even/odd numbers into two new arrays, and assemble the
output by interleaving the two arrays
in-place:
do it like sorting color: swap all odd to the front and even to the back of
the array, then swap pairs again to achieve the output | c*******y
发帖数: 98 | 3 我觉着这个时间复杂度基本和qsort没区别。少partition一层而已。楼上大牛说的
sorting color是怎么模仿的？
来贴个无脑code。。
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
void print(vector& arr){
for (auto& it : arr) cout << it << ", ";
cout << endl;
}
int main (int argc, char** argv) {
vector arr = {2, 4, 6, 8, 10, 1, 3, 5, 7, 9};
print(arr);
int i = 0, j = 9;
while (i < j){
while (i < j && arr[i]&1){i++;}
while (i < j && !(arr[j]&1)){j--;}
swap(arr[i++], arr[j++]);
}
print(arr);
sort(arr.begin(), arr.begin()+5);
sort(arr.begin()+5, arr.end());
print(arr);
return 0;
} | h*******e
发帖数: 1377 | 4 inplace 算法： 快排20个数，然后 左至右扫描， 2个iterator 每次两个循环，
evenI 0开始每次加 2 找到第一个元素为odd的 evenI oddI 1开始每次加2， 找到
第一个元素为 even的oddI swap evenI oddI 的元素 然后继续扫描 直到 evenI 指向
20~~停止。 | s**x
发帖数: 7506 | 5 直接 insertion sort.
Princeton 算法排序时，数目小于15时都直接调用insertion sort.
minimizing
★ 发自iPhone App: ChineseWeb 8.7
【在 d*******u 的大作中提到】
: Can anyone provide an efficient C code for the following probem, minimizing
: the calculating time.
: 20 random numbers, 10 of them are even, the other 10 are odd.
: order the 20 numbers in an alternate way in terms of odd and even.
: Also, all the even numbers should be in an decreasing way. same for odd
: numbers.
: Thanks
|
|
