ArrayList : Find nth occurrence of an Integer

Question

What is the best way to find nth occurrence of a number in ArrayList?

What I know already?

1. To find lastIndexOf the number there is method in List interface, which is implemented in ArrayList class.
2. To find first occurence there is indexOf method.

What I was solving?

In a problem there was a list with different numbers and I have to return index of two numbers whose sum is equal to target number. Ex: List = (1,2,1) & target = 2; Now 1 + 1 =2 and answer will be index of first 1 and second 1.

Note: I have solved this problem & I need answer to the question at the top. Check Solution

What I did?

  public static void main(String[] args)
  {
    List<Integer> list = new ArrayList<Integer>();
    list.add(1);
    list.add(2);
    list.add(1);
    int length = list.size();
    int firstIndex = list.indexOf(1) + 1;
    int secondIndex = firstIndex + list.subList(firstIndex, length).indexOf(1) + 1;
    System.out.println(firstIndex);
    System.out.println(secondIndex);
  }

Answer 1

"a list with all equal numbers" --> {n,n,...,n,n}.

"I have to return index of first two numbers whose sum is equal to target number" Let's suppose target=x. As your list is full of equal numbers, if x/2=n your indexes ll be 0 and 1, if x/2 !=n you wont have any match

---

AFTER QUESTION EDITION

---

    int length=10;
    int target=100;
    int[] tab1= new int[length];
    Object[] tab2= new Object[length];
    Object[] tab2Sorted= new Object[length];

    for (int i = 0; i < tab2Sorted.length; i++) {
        for (int j = i; j < tab2Sorted.length; j++) {
            if(tab2Sorted[i]+tab2Sorted[j]==target){
                //do what you want on objects to get back indexes
            }

        }
        //As tab3 is sorted you dont have to read all the array
        if(tab2Sorted[i]>target/2){
            break;
        }
    }

You just have to change tab2 and tab2Sorted types from Object to a custom type saving the int and his index from first tab

Answer 2

Suppose that your list is not a list, but an array (an arraylist is basically an array once you are done inserting the stuff).

Suppose also that you didn't want to find the index of the first two nums that sum to X, but rather just the two nums (if any).

There is a trivial solution that takes O(n^2) time, where you just iterate each number with all the ones that come after it, and check for the sum.

A better way is to sort the array (which takes O(n*logn)). Now you can, for each number, do a binary search in the array for its complement, i.e. the number which, if summed to it, would result in X. This takes n (each number) * log n (binary search its complement).

But we can't sort, because we want the indexes! Or can't we?

What if we create a copy of the array that, instead of just the value, stores a pair value + originalPosition:

class PosAndValue {
  public final int value;
  public final int pos;
  public PosAndValue(int v, int p) {
    value = v;
    pos = p;
  }
} 

We can now sort an array of these PosAndValue by its value, execute the algorithm just mentioned, and then retrieve the original positions (i.e. indexes), all in n*logn time complexity (and n space complexity).

I'm fairly confident you can't make it much "faster", in terms of complexity. Note that this doesn't mean the code will be faster in any case, but rather that, for sufficiently large inputs (i.e. "big enough" arrays), it will be! for small inputs, as your example, all this overhead may actually make the code slower!

You could make it even better if you knew that the input was limited in range, and then do a boolean bitmap O(n) over the values, but this is a non-specified constraint!

Answer 3

You can build something like this

List<Integer> numbers = new ArrayList<>(); // your list of numbers. Let's say it's {1, 1, 4, 5, 4}
numbers.add(1);
numbers.add(1);
numbers.add(4);
numbers.add(5);
numbers.add(4);
SparseArray<Set<Integer>> occurrences = new SparseArray<>();
for (int i = 0; i < numbers.size(); i++) {
    if (occurrences.indexOfKey(numbers.get(i)) < 0) {
        occurrences.put(numbers.get(i), new HashSet<Integer>());
    }
    Set<Integer> ints = occurrences.get(numbers.get(i)); // get current set
    ints.add(i); // add your new found one
    occurrences.put(numbers.get(i), ints); // put it back into your occurrences set
}

which then will give you a SparseArray of original numbers and sets of these numbers occurences indexes from your original arraylist.

{1=[1, 0], 4=[4, 2], 5=[3]}

Answer 4

This should be most efficient. It uses a sorted version of your array (maintaining references to the original offset) and Collections.binarySearch which should offer best performance.

private Integer[] addsUp(List<Integer> numbers, int value) {
    // Hold the value and it's original offset.
    class No implements Comparable<No> {

        final int n;
        final int o;

        public No(int n, int o) {
            this.n = n;
            this.o = o;
        }

        public No(int n) {
            this(n, -1);
        }

        @Override
        public int compareTo(No o) {
            return Integer.compare(n, o.n);
        }

        @Override
        public String toString() {
            return "{" + n + " @ " + o + "}";
        }
    };
    // Build my list.
    List<No> myNumbers = new ArrayList(numbers.size());
    for (int i = 0; i < numbers.size(); i++) {
        myNumbers.add(new No(numbers.get(i), i));
    }
    // Start sorted.
    Collections.sort(myNumbers);
    // Upper limit of my search.
    int max;
    // Find the value in the numbers.
    No no = new No(value);
    int spot = Collections.binarySearch(myNumbers, no);
    // Did we find it?
    if (spot < 0) {
        // Not found - but this number is nearest to value.
        max = -spot - 1;
    } else {
        // Found ! No number higher than that is relevant.
        max = spot;
    }
    // For each start number.
    for (int first = 0; first < max; first++) {
        No remainder = new No(value - myNumbers.get(first).n);
        // Does that number appear in the list.
        int second = Collections.binarySearch(myNumbers, remainder);
        if (second >= 0) {
            // Found second number! Return original offsets.
            return new Integer[]{myNumbers.get(first).o, myNumbers.get(second).o};
        }
    }
    return null;
}

public void test() {
    List<Integer> numbers = Arrays.asList(1, 2, 1);
    Integer[] two = addsUp(numbers, 2);
    System.out.println("two = " + Arrays.toString(two));
    Integer[] three = addsUp(numbers, 3);
    System.out.println("three = " + Arrays.toString(three));
}

Answer 5

For the question in your title, you can just use a loop together with the subList method of List:

public static void main(String[] args)
{
    List<Integer> list = new ArrayList<Integer>();
    list.add(1);
    list.add(1);
    list.add(1);

    int n = 2;
    int index = -1;
    List<Integer> subList = list;

    for( int i = 0; i < n; i++)
    {
        index = subList.indexOf( 1);

        if( index == -1)
            break;

        System.out.println( i + "th index: " + index);
        subList = subList.subList( index+1, subList.size());
    }
}

For the real problem, finding the nth occurence of a number in a list is not a reliable way of doing it, you are assuming the repeating array element is a divisor of the target number.

Answer 6

public static int nthIndexOf(List<Integer> list, int needle, int n){
    for (int i = 0; i < list.size(); i++) {
        if (list.get(i) == needle) {
            n--;
            if (n == 0) {
                return i;
            }
        }
    }
    return -1;
}

Props to Jon Skeet

Answer 7

  public static void main(String[] args)
  {
    Integer[] numbersList = {1,2,3,4,5,6,7,8,9,10}; //Load your Array here
    List<Integer> list = Arrays.asList(numbersList);
    int targetNumber = 8;  //Load your targetNumber here

    int currrentVal = 0;
    int nextVal = 0;
    int i = 0;
    int j = 0;
    boolean found = false;
    for(i=0;i<list.size();i++) {
        currrentVal = list.get(i);          
        for(j=currrentVal+1;j<list.size();j++) {
            nextVal = list.get(j);              
            if(targetNumber == currrentVal+nextVal) {
                found = true;
                break;
            }
        }
        if(found) {
            break;
        }
    }
    if(found) {
        System.out.println("firstIndex  : "+i);
        System.out.println("secondIndex : "+j);
    } else {
        System.out.println(" No match found");
    }
  }