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

问题是，函数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;
}

非常感谢你。

Answer 1

鉴于您的约束，除了O（n）之外没有更好的搜索算法。原因如下：

• 您的数据包含0到100,000,000之间的“随机”值
• 您想要收集与给定数字匹配的所有值（在您的示例中，4）
• 您无法对列表进行排序（这会产生额外的O（n * log（n））开销）

如果您可以将数据集移动到不同的数据结构（例如Map），那么这种方法可能会变得更好。然后，您将因加载数据而受到O（n）惩罚，但您可以在此之后的恒定时间内找到值。

Answer 2

如果你使用Map，其中key是你的输入值而值是频率，那么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，因为它更紧凑，并且不会为最后一个字符添加冗余空间。