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?
我已经知道什么?
- 找到lastIndexOf List 接口中存在的方法的数量，该方法在 ArrayList 类中实现.
- 要找到第一次出现，有 indexOf 方法.
- To find lastIndexOf the number there is method in List interface, which is implemented in ArrayList class.
- To find first occurence there is indexOf method.
我在解决什么问题?
在一个问题中有一个包含不同数字的列表，我必须返回总和等于目标数字的两个数字的索引.例如:List = (1,2,1) &目标 = 2;现在 1 + 1 =2 并且答案将是第一个 1 和第二个 1 的索引.
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屋！
