CODEWITHSUNDEEP
javaarraylisttime-complexity
Andrew Prawira
Andrew Prawira

Reputation: 61

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

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

Upvotes: 4

Views: 137

Answers (2)

Anatolii
Anatolii

Reputation: 14660

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.

Upvotes: 3

Makoto
Makoto

Reputation: 106430

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.

Upvotes: 4

Related Questions