ArrayList :查找整数的第 n 次出现
ArrayList : Find nth occurrence of an Integer
在 ArrayList 中查找数字第 n 次出现的最佳方法是什么?
我已经知道了什么?
- 查找lastIndexOf数在List接口中有方法,在ArrayList中实现class。
- 要找到第一次出现,有 indexOf 方法。
我解决了什么?
在一个问题中,有一个包含不同数字的列表,我必须 return 两个数字的索引,其总和等于目标数字。
例如:List = (1,2,1) & target = 2;
现在 1 + 1 =2
和答案将是第一个 1 和第二个 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);
}
"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" 让我们假设目标=x。
由于您的列表充满了相等的数字,如果 x/2=n 您的索引将是 0 和 1,如果 x/2 !=n 您将没有任何匹配项
问题版后
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;
}
}
您只需将 tab2 和 tab2Sorted 类型从 Object 更改为自定义类型,保存第一个 tab 中的 int 和他的索引
对于你标题中的问题,你可以直接使用循环和List的subList方法:
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());
}
}
对于实际问题,查找列表中第 n 次出现的数字并不是一种可靠的方法,您假设重复数组元素是目标数字的约数。
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;
}
支持Jon Skeet
假设您的列表不是一个列表,而是一个数组(一旦您完成插入,数组列表基本上就是一个数组)。
还假设您不想找到总和为 X 的前两个数字的索引,而只想找到这两个数字(如果有的话)。
有一个需要 O(n^2) 时间的简单解决方案,您只需将每个数字与它后面的所有数字进行迭代,然后检查总和。
更好的方法是对数组进行排序(这需要 O(n*logn))。现在,对于每个数字,您可以在数组中对其补码进行二进制搜索,即如果将其相加,将得到 X 的数字。这需要 n(每个数字)* log n(二进制搜索其补码) .
但是我们不能排序,因为我们需要索引!或者我们不能?
如果我们创建一个数组的副本,而不只是值,存储一对值 + 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 space复杂度)。
我相当有信心,就复杂性而言,您不会做得太多 "faster"。请注意,这并不意味着代码在任何情况下都会更快,而是说,对于足够大的输入(即 "big enough" 数组),它会更快!对于小输入,例如您的示例,所有这些开销实际上可能会使代码变慢!
如果您知道输入的范围有限,然后对值执行 O(n) 布尔位图,您可以做得更好,但这是一个未指定的约束!
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");
}
}
你可以构建这样的东西
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
}
然后会给你一个原始数字的 SparseArray 和原始数组列表中这些数字出现索引的集合。
{1=[1, 0], 4=[4, 2], 5=[3]}
这应该是最有效的。它使用数组的排序版本(维护对原始偏移量的引用)和 Collections.binarySearch
应该提供最佳性能。
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));
}
在 ArrayList 中查找数字第 n 次出现的最佳方法是什么?
我已经知道了什么?
- 查找lastIndexOf数在List接口中有方法,在ArrayList中实现class。
- 要找到第一次出现,有 indexOf 方法。
我解决了什么?
在一个问题中,有一个包含不同数字的列表,我必须 return 两个数字的索引,其总和等于目标数字。
例如:List = (1,2,1) & target = 2;
现在 1 + 1 =2
和答案将是第一个 1 和第二个 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);
}
"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" 让我们假设目标=x。 由于您的列表充满了相等的数字,如果 x/2=n 您的索引将是 0 和 1,如果 x/2 !=n 您将没有任何匹配项
问题版后
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;
}
}
您只需将 tab2 和 tab2Sorted 类型从 Object 更改为自定义类型,保存第一个 tab 中的 int 和他的索引
对于你标题中的问题,你可以直接使用循环和List的subList方法:
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());
}
}
对于实际问题,查找列表中第 n 次出现的数字并不是一种可靠的方法,您假设重复数组元素是目标数字的约数。
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;
}
支持Jon Skeet
假设您的列表不是一个列表,而是一个数组(一旦您完成插入,数组列表基本上就是一个数组)。
还假设您不想找到总和为 X 的前两个数字的索引,而只想找到这两个数字(如果有的话)。
有一个需要 O(n^2) 时间的简单解决方案,您只需将每个数字与它后面的所有数字进行迭代,然后检查总和。
更好的方法是对数组进行排序(这需要 O(n*logn))。现在,对于每个数字,您可以在数组中对其补码进行二进制搜索,即如果将其相加,将得到 X 的数字。这需要 n(每个数字)* log n(二进制搜索其补码) .
但是我们不能排序,因为我们需要索引!或者我们不能?
如果我们创建一个数组的副本,而不只是值,存储一对值 + 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 space复杂度)。
我相当有信心,就复杂性而言,您不会做得太多 "faster"。请注意,这并不意味着代码在任何情况下都会更快,而是说,对于足够大的输入(即 "big enough" 数组),它会更快!对于小输入,例如您的示例,所有这些开销实际上可能会使代码变慢!
如果您知道输入的范围有限,然后对值执行 O(n) 布尔位图,您可以做得更好,但这是一个未指定的约束!
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");
}
}
你可以构建这样的东西
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
}
然后会给你一个原始数字的 SparseArray 和原始数组列表中这些数字出现索引的集合。
{1=[1, 0], 4=[4, 2], 5=[3]}
这应该是最有效的。它使用数组的排序版本(维护对原始偏移量的引用)和 Collections.binarySearch
应该提供最佳性能。
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));
}