Is there any search method better than O(n) for ArrayList?

Question

I have a question from a quiz :

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

These are the default codes, and we're free to place any codes anywhere:

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

The Question is, what is the most efficient method for function pick() which is better than O(n) ?

This is my version of 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;
}

How about iterating once over list to build (and cache) `Map>` which would group all equal values? Building process would take O(n) time, but then each `map.get(value)` call would be O(1). — Pshemo, Aug 31 '18 at 16:39
Your version isn't o(n). You are using quadratic string concatenation. — Andy Turner, Aug 31 '18 at 16:39
If you need do the search many times, you can sort it with `nlogn`(quick sort), then the search will get `logn`(binary search). https://stackoverflow.com/questions/11227809/why-is-it-faster-to-process-a-sorted-array-than-an-unsorted-array — xingbin, Aug 31 '18 at 16:39
All the List have O(n) complexity for searching. You can use Trees/Maps which have O(log(n)) for both insertion as well as searching and use twice the space for your requirement. — Ashraff Ali Wahab, Aug 31 '18 at 16:52

score 4 · Answer 1 · answered Aug 31 '18 at 16:51

Given your constraints, there is no better searching algorithm besides O(n). The reason for this:

Your data contains "randomized" values between 0 and 100,000,000
You want to collect all values which match a given number (in your example, 4)
You have no ability to sort the list (which would incur an additional O(n*log(n)) overhead)

The only way this could get better is if you could move your data set to a different data structure, such as a Map. Then, you would incur an O(n) penalty for loading the data, but you'd be able to find the values in constant time after that.

Yes, i think it is the only way for now. Haven't found any better choices yet. — Andrew Prawira, Aug 31 '18 at 17:09

Anatolii · Answer 2 · 2018-08-31T17:01:21.357

If you use a Map in which key is your input value and a value is the frequency then Map will find a key in O(1) time. The string constructing will be proportional to the frequency of a key though. So, the code could be as follows:

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

Edit

As suggested by @Pshemo, StringJoiner is used instead of StringBuilder as it's more compact and doesn't add a redundant space for the last character.

No problem. BTW `sb.append("\n");` is probably unnecessary since it should be up to user do decide if he wants to print returned values as separate lines or in one line. BTW StringJoiner would be better than StringBuilder since it would prevent adding space after last element. — Pshemo, Aug 31 '18 at 16:50

Is there any search method better than O(n) for ArrayList?

2 Answers2