我有一个测验问题:
If input data of randomList are 4 5 1 2 3 4
Results are:
pick(4) -> 4 4
pick(1) -> 1
pick(2) -> 2
pick(6) -> there is no value
这些是默认代码,我们可以随意将任何代码放在任何地方:
public static void main(String[] args){
List<Integer> randomList = new ArrayList<>();
for(int i = 0; i < 100000000; i++) {
randomList.add(new Random().nextInt());
}
.....
System.out.println("result = " + pick(new Random().nextInt()));
问题是,函数 pick() 的最有效方法是什么比 O(n) 更好?
这是我的 O(n) 版本:
static List<Integer> list2 = new ArrayList<>();
public static void main(String[] args){
List<Integer> randomList = new ArrayList<>();
for(int i = 0; i < 10; i++) {
randomList.add(new Random().nextInt(5)+1);
}
list2 = randomList;
System.out.println("result = " + pick(new Random().nextInt(5)+1));
}
public static String pick(int rand) {
String result = "";
System.out.println("search = " + rand);
for(Integer s : list2) {
if(s == rand) {
result = result + " " + rand;
}
}
return result;
}
最佳答案
鉴于您的限制,除了 O(n) 之外没有更好的搜索算法。这样做的原因:
- 您的数据包含 0 到 100,000,000 之间的“随机”值
- 您想收集与给定数字(在您的示例中为 4)匹配的所有值
- 您无法对列表进行排序(这会产生额外的 O(n*log(n)) 开销)
如果您可以将数据集移动到不同的数据结构(例如 Map),唯一可以改善这一点的方法。然后,您将因加载数据而受到 O(n) 的惩罚,但之后您将能够在恒定时间内找到这些值。
关于java - ArrayList 有没有比 O(n) 更好的搜索方法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52119551/