给定一个 int 数组，长度 200，里面的元素是 0-2000 内的随机数。找出 50-100 之间的所有数，并排序。大家有什么思路？
marginleft · Jul 9, 2015 · 4043 viewsThis topic created in 3951 days ago, the information mentioned may be changed or developed.
Supplement 1 · Jul 10, 2015
感谢大家回复。
我一开始也想用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 Jul 9, 2015
先排个序再找 50 - 100 的就好了
|
 |
2
loveuqian Jul 9, 2015 via iPhone
初学者只能想到先遍历找出再排序了
|
 |
3
batman2010 Jul 9, 2015
最大堆。
|
 |
4
txx Jul 9, 2015
2000 直接做基数排序吧....
|
 |
5
chlx Jul 9, 2015
如果不重复的话bit记录50-100. 最后按顺序输出. O(N).
|
 |
6
publicID001 Jul 9, 2015 via Android
统计50-100 之间的所有数出现次数，输出
另外这种数据规模就算暴力也没什么压力啊 |
 |
7
Kilerd Jul 9, 2015
先sort,再用二分法找50和100，就可以了吧
|
 |
8
otakustay Jul 9, 2015
才200个数，显然开200个空位直接哈希排序了，冲撞就用开链表解决
|
 |
9
akira Jul 9, 2015
这个数据量，随便什么方法都可以了呀。
先排序在过滤或者先过滤再排序都毫无压力的。 而且排序直接冒泡都没问题呀 |
 |
10
also24 Jul 9, 2015
我可以推荐一下Bogo排序嘛？
|
 |
11
scream7 PRO 计数排序.
|
 |
12
18000rpm Jul 9, 2015 via Android
想到快排，并且在每次分区的过程中遇到 50～100 之外的直接丢掉。
|
 |
14
acros Jul 9, 2015
空间换时间吗？遍历一遍。
声明一个200长度的数组numArray[200]，memset一下。 遍历一遍numArray[i]++，就得到所有数的排序表了 |
|
15
acros Jul 9, 2015
上面数字说错了。等下我改改。
|
|
16
acros Jul 9, 2015
numArray[2000];
原数组遍历src[i], numArray[src[i]]++ 然后查看下numArray从50到100项非零的。 |
 |
17
hahastudio Jul 9, 2015
桶排啊，反正就 51 个位置
|
 |
18
cloud107202 Jul 9, 2015
桶排+1
|
 |
19
IwfWcf Jul 9, 2015
才 200 长度，怎么搞都可以啦……
|
 |
20
liuhaotian Jul 9, 2015 via iPhone
数组[50，100] x[M]++
|
 |
21
msg7086 Jul 9, 2015
最容易实现的方法就是堆排序了吧。开个priority queue什么的然后一边判断一边插♂，跑完就能拿到结果了。
|
 |
22
lzdhlsc Jul 10, 2015
桶排 O(n)
|
 |
23
initdrv Jul 10, 2015 via iPhone
身为一名默默无闻的JAVA新手，表示只能想到用Arrays的sort排序后，再用二分查找？分别得到不小于50和不大于100的角标？最后循环输出？😔😳
|
 |
24
poke707 Jul 10, 2015
LZ其实使用了twitter sort的一个变种
https://github.com/ExPHAT/twitter-sort |
 |
25
marginleft OP @poke707 为什么这么说呢？
|
Select Language