ArrayList:查找整数的第n次出现 [英] ArrayList : Find nth occurrence of an Integer

问题描述

在ArrayList中找到数字的第n个出现的最佳方法是什么?

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

我已经知道什么?

1. 要找到 indexOf 方法.

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.

我正在解决什么?

在一个问题中，存在一个具有不同数字的列表，我必须返回两个数字的索引，其总和等于目标数字. 例如:List = (1,2,1) & target = 2; 现在1 + 1 =2和答案将是前1和后2的索引.

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

我做了什么?

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

推荐答案

假定您的列表不是列表，而是一个数组(一旦您完成插入操作，arraylist基本上就是一个数组).

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

还假设您不想找到总和为X的前两个数字的索引，而只是找到两个数字(如果有的话).

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).

有一个简单的解决方案需要O(n ^ 2)的时间，您只需将每个数字与后面的所有数字进行迭代，然后检查总和即可.

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.

更好的方法是对数组进行排序(需要O(n * logn)).现在，您可以针对每个数字在数组中进行二进制搜索以查找其补数，即，如果对数字求和，则将得出X.这需要n(每个数字)* log n(二进制搜索其补数)

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?

如果我们创建数组的副本，而不是仅仅存储值，那么将存储对值+ originalPosition:

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

我们现在可以按其值对这些PosAndValue的数组进行排序，执行上述算法，然后检索原始位置(即索引)，所有这些都以n * logn时间复杂度(和n空间复杂度)进行.

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!

如果您知道输入范围有限，然后对值进行布尔位图O(n)，则可以做得更好，但这是未指定的约束！

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!

这篇关于ArrayList:查找整数的第n次出现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！