ArrayList 有没有比 O(n) 更好的搜索方法？

Question

我有一个测验的问题：

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()));

问题是，比 O(n) 更好的函数 pick() 最有效的方法是什么？

这是我的 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;

}

Answer 1

鉴于您的限制，除了 O(n) 之外，没有更好的搜索算法。原因如下：您的数据包含 0 到 100,000,000 之间的“随机”值您想收集与给定数字匹配的所有值（在您的示例中为 4）您无法对列表进行排序（这会产生额外的 O(n*log(n)) 开销）唯一可以改善的方法是，如果您可以将数据集移动到不同的数据结构，例如 Map。然后，您会因加载数据而遭受 O(n) 惩罚，但之后您将能够在恒定时间内找到这些值。

Answer 2

如果您使用Map其中的键是您的输入值，而值是频率，则将及时Map找到键O(1)。但是，字符串构造将与键的频率成正比。所以，代码可能如下：Map<Integer, Integer> mapList = new HashMap<>();public static void main(String[] args){&nbsp; &nbsp; for(int i = 0; i < 10; i++) {&nbsp; &nbsp; &nbsp; &nbsp; int key = new Random().nextInt(5)+1;&nbsp; &nbsp; &nbsp; &nbsp; if (mapList.contains(key)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; mapList.put(key, mapList.get(key) + 1);&nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; mapList.put(key, 1);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp;&nbsp; &nbsp; }&nbsp; &nbsp; System.out.println("result = " + pick(new Random().nextInt(5)+1));}public static String pick(int rand) {&nbsp; &nbsp; Integer count = mapList.get(rand);&nbsp; &nbsp; if (count == null) {&nbsp; &nbsp; &nbsp; &nbsp; return "";&nbsp; &nbsp; }&nbsp;&nbsp; &nbsp; StringJoiner sj = new StringJoiner(" ");&nbsp; &nbsp; for (int i = 0; i < count; i++) {&nbsp; &nbsp; &nbsp; &nbsp; sj.add(rand);&nbsp; &nbsp; }&nbsp; &nbsp; return sj.toString();}编辑正如@Pshemo 所建议的那样，StringJoiner使用它代替 StringBuilder，因为它更紧凑，并且不会为最后一个字符添加多余的空间。