给定一个 int 数组，长度 200，里面的元素是 0-2000 内的随机数。找出 50-100 之间的所有数，并排序。大家有什么思路？
marginleft · 2015-07-09 16:36:41 +08:00 · 3439 次点击这是一个创建于 3424 天前的主题，其中的信息可能已经有所发展或是发生改变。
第 1 条附言 · 2015-07-10 09:13:00 +08:00
感谢大家回复。
我一开始也想用bitset，来初始化一个长度是2000的数组。但是后来看到大家的初始化max-min=50个桶就能解决，感觉这确实是一个很好的方法，我用java写了一个demo：
import java.util.Arrays;
import java.util.Random;
public class SortTest {
public static void main(String[] args) {
// 初始化
int inputArrLength = 200;
int maxValue = 2000;
int min = 50, max = 100;
int input[] = new int[inputArrLength];
Random rand = new Random();
System.out.println("input:");
for (int i = 0; i < input.length; i++) {
input[i] = rand.nextInt(maxValue);
if (input[i] >= min && input[i] < max) {
System.out.print(input[i] + ",");
}
}
System.out.println();
// bitset排序
int bitset[] = new int[maxValue];
Arrays.fill(bitset, 0);
for (int i : input) {
if (i >= min && i < max) {
bitset[i]++;
}
}
for (int i = 0; i < bitset.length; i++) {
if (bitset[i] > 0) {
for (int j = 0; j < bitset[i]; j++) {
System.out.print(i + ",");
}
}
}
System.out.println();
// 桶排序
int bucket[] = new int[max - min];
Arrays.fill(bucket, 0);
for (int i : input) {
if (i >= min && i < max) {
bucket[i - min]++;
}
}
for (int i = 0; i < bucket.length; i++) {
if (bucket[i] > 0) {
for (int j = 0; j < bucket[i]; j++) {
System.out.print((i + min) + ",");
}
}
}
}
}
我一开始也想用bitset，来初始化一个长度是2000的数组。但是后来看到大家的初始化max-min=50个桶就能解决，感觉这确实是一个很好的方法，我用java写了一个demo：
import java.util.Arrays;
import java.util.Random;
public class SortTest {
public static void main(String[] args) {
// 初始化
int inputArrLength = 200;
int maxValue = 2000;
int min = 50, max = 100;
int input[] = new int[inputArrLength];
Random rand = new Random();
System.out.println("input:");
for (int i = 0; i < input.length; i++) {
input[i] = rand.nextInt(maxValue);
if (input[i] >= min && input[i] < max) {
System.out.print(input[i] + ",");
}
}
System.out.println();
// bitset排序
int bitset[] = new int[maxValue];
Arrays.fill(bitset, 0);
for (int i : input) {
if (i >= min && i < max) {
bitset[i]++;
}
}
for (int i = 0; i < bitset.length; i++) {
if (bitset[i] > 0) {
for (int j = 0; j < bitset[i]; j++) {
System.out.print(i + ",");
}
}
}
System.out.println();
// 桶排序
int bucket[] = new int[max - min];
Arrays.fill(bucket, 0);
for (int i : input) {
if (i >= min && i < max) {
bucket[i - min]++;
}
}
for (int i = 0; i < bucket.length; i++) {
if (bucket[i] > 0) {
for (int j = 0; j < bucket[i]; j++) {
System.out.print((i + min) + ",");
}
}
}
}
}
 |
1
sumhat 2015-07-09 16:42:52 +08:00
先排个序再找 50 - 100 的就好了
|
 |
2
loveuqian 2015-07-09 16:43:00 +08:00 via iPhone
初学者只能想到先遍历找出再排序了
|
 |
3
batman2010 2015-07-09 16:46:17 +08:00
最大堆。
|
 |
4
txx 2015-07-09 16:51:24 +08:00
2000 直接做基数排序吧....
|
 |
5
chlx 2015-07-09 16:52:22 +08:00
如果不重复的话bit记录50-100. 最后按顺序输出. O(N).
|
 |
6
publicID001 2015-07-09 16:57:21 +08:00 via Android
统计50-100 之间的所有数出现次数，输出
另外这种数据规模就算暴力也没什么压力啊 |
 |
7
Kilerd 2015-07-09 16:58:36 +08:00
先sort,再用二分法找50和100，就可以了吧
|
 |
8
otakustay 2015-07-09 17:15:12 +08:00
才200个数，显然开200个空位直接哈希排序了，冲撞就用开链表解决
|
 |
9
akira 2015-07-09 17:46:07 +08:00
这个数据量，随便什么方法都可以了呀。
先排序在过滤或者先过滤再排序都毫无压力的。 而且排序直接冒泡都没问题呀 |
 |
10
also24 2015-07-09 17:59:32 +08:00
我可以推荐一下Bogo排序嘛？
|
 |
11
scream7 2015-07-09 18:17:47 +08:00
计数排序.
|
 |
12
18000rpm 2015-07-09 18:58:50 +08:00 via Android
想到快排，并且在每次分区的过程中遇到 50～100 之外的直接丢掉。
|
 |
14
acros 2015-07-09 20:43:59 +08:00
空间换时间吗？遍历一遍。
声明一个200长度的数组numArray[200]，memset一下。 遍历一遍numArray[i]++，就得到所有数的排序表了 |
|
15
acros 2015-07-09 20:44:58 +08:00
上面数字说错了。等下我改改。
|
|
16
acros 2015-07-09 20:48:54 +08:00
numArray[2000];
原数组遍历src[i], numArray[src[i]]++ 然后查看下numArray从50到100项非零的。 |
 |
17
hahastudio 2015-07-09 20:51:48 +08:00
桶排啊，反正就 51 个位置
|
 |
18
cloud107202 2015-07-09 21:23:09 +08:00
桶排+1
|
 |
19
IwfWcf 2015-07-09 22:42:36 +08:00
才 200 长度，怎么搞都可以啦……
|
 |
20
liuhaotian 2015-07-09 22:44:40 +08:00 via iPhone
数组[50，100] x[M]++
|
 |
21
msg7086 2015-07-09 22:49:42 +08:00
最容易实现的方法就是堆排序了吧。开个priority queue什么的然后一边判断一边插♂，跑完就能拿到结果了。
|
 |
22
lzdhlsc 2015-07-10 01:54:56 +08:00
桶排 O(n)
|
 |
23
initdrv 2015-07-10 02:26:56 +08:00 via iPhone
身为一名默默无闻的JAVA新手，表示只能想到用Arrays的sort排序后，再用二分查找？分别得到不小于50和不大于100的角标？最后循环输出？😔😳
|
 |
24
poke707 2015-07-10 12:41:30 +08:00
LZ其实使用了twitter sort的一个变种
https://github.com/ExPHAT/twitter-sort |
 |
25
marginleft OP @poke707 为什么这么说呢？
|
Select Language