S*******C
发帖数: 822 | 1 10 million的数组，数字是8bit的非负数，排序
count sort搞定
follow up，10 million的item class，item有rating和name，根据rating sort。
rating和上面一样也是8bit unsign.
Amazon intern问题 |
a****r
发帖数: 87 | 2 实现item class的时候实现一个比较的function -里面根据rating 比较大小。 |
S*******C
发帖数: 822 | 3 这样的话是调用Collections.sort()方法，这个是mergeSort()
时间复杂度是O(NlogN） 而不是counting sort 的O(N)
【在 a****r 的大作中提到】
: 实现item class的时候实现一个比较的function -里面根据rating 比较大小。
|
d******e
发帖数: 2265 | 4 8比特开一个256的数组好了
不用调用库函数
第一计数
第二搞一个seq
【在 S*******C 的大作中提到】
: 10 million的数组，数字是8bit的非负数，排序
: count sort搞定
: follow up，10 million的item class，item有rating和name，根据rating sort。
: rating和上面一样也是8bit unsign.
: Amazon intern问题
|
m*****g
发帖数: 71 | 5 两种办法：
1.搞256个链表，rating是x的就放在x号链表里，最后顺序输出各个链表里的object，
如果要求stable的话，要注意插入位置和扫描顺序。
2.简单的计数数组，计完数之后，把计数变换成该rating对象在输出数组中的下一个
index，假设输入有N个object
a[255] = N - a[255];
for (int i = 254; i >= 0; --i) {
a[i] = a[i + 1] - a[i];
}
最后输出时，从前往后扫输入数组，rating为x的，放在输出数组的a[x]位置，然后+
+a[x]。这个屏记忆写的，不保证完全正确，建议查一下CRLS。 |
