How to get indexOf element which isn't the first

Question

Assumed

ArrayList<Integer> list =  Arrays.asList(new Integer[] {1,2,3,4,5,6,1,8,9});

Find second occurence

I want to get the index of the second finding of the (multiple) contained element "1" but list.indexOf(1) will always return 0 (as it's the first finding).

Performance

I want to do this without using loops like for or while. Since I need it for a game, using loops wouldn't be efficient at all.

EDIT: Is there any way to get "indexOf" some element without iterator ?

use `subList` and then `indexOf` (but not more efficient, but readable IMO) — user85421, Mar 19 '19 at 18:53
Yeah but lets say the array is [1,2,3,1,4,1] and i would like to get the middle one — Martin Lukas, Mar 19 '19 at 18:55

score 5 · Accepted Answer · answered Mar 19 '19 at 18:55

You cannot do this without iterating.
indexOf iterates, for example.

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

Same is valid for lastIndexOf.
As you can see no Iterator<Integer> is used at all, if that is what worries you.

And, btw, this isn't a performance concern.
Do you have arrays with millions of elements? If you have, consider changing data structure type.

HariUserX · Answer 2 · 2019-03-19T19:10:33.717

If you are very much concerned about performance, use a HashMap<Integer, List<Integer>>. Then if your want n'th occurence of an element m, you can do map.get(m).get(n). Your map contains elements and their corresponding indexes.

Once your map is built, the time complexity for your query would be O(1)

Example:

    public static void main(String[] args){
        int[] a = {1, 2, 1, 3, 4, 1};
        Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();

        for(int i = 0; i < a.length; i++){
            if(map.containsKey(a[i])){
                map.get(a[i]).add(i);
            }else{
                map.put(a[i], new ArrayList<Integer>());
                map.get(a[i]).add(i);
            }
        }

        // second index of 1. Note that index starts from 0.

        System.out.println(map.get(1).get(1));
    }

Result:

2

score 0 · Answer 3 · edited Mar 19 '19 at 21:20

0

list.indexOf(1, list.indexOf(1) + 1);

The first parameter 1 being the object to be searched. The second parameter list.indexOf(1) + 1 being the starting index for the search.

edited Mar 19 '19 at 21:20

hc_dev

8,389
1
26
38

answered Mar 19 '19 at 18:55

myworkname

1

1

that is for `String`s not for `List`s, at least so in Java 11 – user85421 Mar 19 '19 at 18:55
@CarlosHeuberger you are correct. Although OP changed their question anyway. – myworkname Mar 19 '19 at 19:05
You could [edit] your answer and post the link to the documentation of your mentioned method `indexOf(Object what, int where)`. I doubt it can be used on asked `List` interface or its implementation [ArrayList](https://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html#indexOf(java.lang.Object)). – hc_dev Mar 19 '19 at 19:15
Your approach is good. It could be implemented using `subList` in combination with `indexOf`; see [this answer](https://stackoverflow.com/q/32461150) to _ArrayList : Find nth occurrence of an Integer_ – hc_dev Mar 19 '19 at 19:26

score 0 · Answer 4 · answered Mar 19 '19 at 19:33

0

list.subList(list.indexOf(1) + 1, list.size()).indexOf(1)

answered Mar 19 '19 at 19:33

StackUser2204

126
1
6

How to get indexOf element which isn't the first

Assumed

Find second occurence

Performance

4 Answers4