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

Question

我有一个测验的问题：If input data of randomList are 4 5 1 2 3 4Results are:pick(4) -> 4 4pick(1) -> 1pick(2) -> 2pick(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){

    for(int i = 0; i < 10; i++) {

        int key = new Random().nextInt(5)+1;

        if (mapList.contains(key)) {

            mapList.put(key, mapList.get(key) + 1);

        } else {

            mapList.put(key, 1);

        } 

    }

    System.out.println("result = " + pick(new Random().nextInt(5)+1));

}

public static String pick(int rand) {

    Integer count = mapList.get(rand);

    if (count == null) {

        return "";

    } 

    StringJoiner sj = new StringJoiner(" ");

    for (int i = 0; i < count; i++) {

        sj.add(rand);

    }

    return sj.toString();

}

编辑

正如@Pshemo 所建议的那样，StringJoiner使用它代替 StringBuilder，因为它更紧凑，并且不会为最后一个字符添加多余的空间。