Java 在整数数组列表中查找最大的数字序列
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/18994686/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Find the largest sequence of numbers in an integer arraylist
提问by
This is what I've gotten so far. What I've tried to do is go through and find the sequence using greater or equals too in an if statement. Then when that value no longer is greater or equal to the preveious number it goes into the else statement which records that sequence number and resets it so the count can begin again. All these sequence values are saved in an arraylist so that when I'm all done I can just do a simple comparison to find the greatest sequence number and return that. I need help with my first if/else statement that gathers the sequence data because I'm pretty sure this is where my issues are happening.
这是我到目前为止所得到的。我试图做的是在 if 语句中遍历并找到使用更大或等于的序列。然后，当该值不再大于或等于前一个数字时，它会进入 else 语句，该语句记录该序列号并重置它，以便可以再次开始计数。所有这些序列值都保存在一个数组列表中，这样当我完成所有操作后，我可以做一个简单的比较来找到最大的序列号并返回它。我需要关于收集序列数据的第一个 if/else 语句的帮助，因为我很确定这是我的问题发生的地方。
public class LongestSequence {
public static int getMaxSequence(ArrayList<Integer> list) {
int sequence = 0;
ArrayList<Integer> temp = new ArrayList<Integer>();
for (int i = 0; i < list.size() - 1; i++) {
//this is where things go wrong. I think.
if (list.get(i + 1) >= list.get(i)) {
sequence++;
} else {
//record the number in your arraylist
temp.add(sequence);
//reset count to 0
sequence = 0;
}
}
int greatestnum = 0;
for (int i = 0; i < temp.size() - 1; i++) {
if (temp.get(i) < temp.get(i + 1)) {
greatestnum = temp.get(i + 1);
} else {
greatestnum = temp.get(i);
}
}
return greatestnum;
}
采纳答案by arshajii
You shouldn't have to use a temporary list for this. Just loop through the array or list with a counter and increment for each element that is greater than or equal to the previous. Use another variable to store the maximum:
您不应该为此使用临时列表。只需使用计数器循环遍历数组或列表，并为每个大于或等于前一个元素的元素递增。使用另一个变量来存储最大值：
int[] a = { 1, 2, 3, 4, 0, 19, 1, 1, 2, 2, 3, 3, 2 };
int count = 1, max = 1;
for (int i = 1; i < a.length; i++) {
if (a[i] >= a[i - 1]) {
count++;
} else {
count = 1;
}
if (count > max) {
max = count;
}
}
System.out.println(max);
6
Here, countis the number of contiguous and sorted elements. We increment it while we're on a continuous/increasing streak. Once this streak breaks (elseclause), we check if countis greater than max, our variable for storing the maximum count: if it is, we set maxto count. We then set countback to 1, since in the elseclause we know our streak has ended and we'll need to start over.
这里，count是连续和排序元素的数量。当我们处于连续/增加的连续性时，我们会增加它。一旦这个连续性中断（else子句），我们检查是否count大于max，我们用于存储最大计数的变量：如果是，我们设置max为count。然后我们重新设置count为 1，因为在else子句中我们知道我们的连胜已经结束，我们需要重新开始。
(I've used an array here, but it should be trivial to convert the above code to work with lists).
（我在这里使用了一个数组，但将上面的代码转换为使用列表应该很简单）。
回答by ibtarek
It may be done recursively :
它可以递归完成：
public static int getMaxSequence(List<Integer> list){
if (list == null) return 0;
if (list.size() == 1) return 1;
return getMaxSequence(list.get(0), list.subList(1, list.size()),1);
}
public static int getMaxSequence(int head, List<Integer> tail,int soFar) {
if (tail == null) return 0;
if (tail.size()==0) return soFar;
if (head <= tail.get(0)){
soFar++; //the sequence gets bigger
}else{
soFar = 1; //restart the sequence
}
final int nextSeq = getMaxSequence(tail.get(0),tail.subList(1, tail.size()),soFar);
//finally return what we have found so far or the longest sequence down the list
return Math.max(soFar, nextSeq);
}
And used like this :
并像这样使用：
final List<Integer> list = Arrays.asList(1, 2, 3, 4, 0, 19, 1, 1, 2, 2, 3, 3, 2);
System.out.println(getMaxSequence(list));
Although it should be faster with instances of LinkedList, it should work with any List.
尽管使用 LinkedList 实例应该更快，但它应该适用于任何 List。
回答by Roberto Navarro
For the sake of keeping the data structures originally used-- this is how I would propose solving this issue.
为了保持最初使用的数据结构——这就是我建议解决这个问题的方式。
Testing params:
测试参数：
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(12);
list.add(12345);
list.add(999999999);
System.out.println(getMaxSequence(list));
Now, I simply compare all the values to indx 0, but totally not necessary :)
现在，我只是将所有值与 indx 0 进行比较，但完全没有必要:)
public static int getMaxSequence(ArrayList<Integer> list) {
int indx = 0;
int currmax = 0;
currmax = list.get(indx).toString().length();
while (indx < list.size()) {
if (currmax <= list.get(indx).toString().length()) {
currmax = list.get(indx).toString().length();
} else
return currmax;
// list.remove(indx);
indx++;
}
return currmax;
}
回答by ashokhein
The longest increasing subsequence problem is a dynamic programming problem that calculates the length of a non-contiguous subsequence from a given sequence
最长递增子序列问题是一个动态规划问题，它根据给定的序列计算非连续子序列的长度
import java.io.*;
public class CandidateCode
{
public static int longestSeq(int[]seq){
int[]L=new int[seq.length];
L[0]=1;
for(int i=1;i<L.length;i++){
int maxn=0;
for(int j=0;j<i;j++){
if(seq[j]<seq[i]&&L[j]>maxn){
maxn=L[j];
}
}
L[i]=maxn+1;
}
int maxi=0;
for(int i=0;i<L.length;i++){
if(L[i]>maxi){
maxi=L[i];
}
}
return(maxi);
}
}
回答by Barry Keepence
This is similar to the answer from arshajii but has the fix suggested for when the sequence is at the end of the array. This answer also checks for monotonically increasing or equal numbers.
这类似于来自 arshajii 的答案，但建议在序列位于数组末尾时进行修复。此答案还检查单调递增或相等的数字。
https://jsfiddle.net/ppy6tdt8/
https://jsfiddle.net/ppy6tdt8/
var a = [ 1, 2, 3, 4, 0, 19, 1, 1, 2, 2, 3, 3, 2 ];
var b = [1,2,4,5,7,8,9];
function getSpan ( a ) {
if (a.length < 2) {
return 1;
}
var count = 1, max = 1;
for (var i = 1; i < a.length; i++) {
if (a[i] == a[i - 1]+1 || a[i] == a[i - 1]) {
if (++count > max) {
max = count;
}
} else {
count = 1;
}
}
return ( max );
}
console.log (getSpan(a));
console.log (getSpan(b));
回答by akki
You can use Collections from java util itself and can find from arraylist explicitly.
您可以使用 java util 本身的 Collections，也可以显式地从 arraylist 中查找。
ArrayList<Integer> list = new ArrayList<Integer>();
// Here add data to ArrayList
int maxNum = Collections.max(list);
maxNum is Biggest integer from a list.
maxNum 是列表中的最大整数。
回答by Karan Khanna
You can use the following algorithm to get the largest sequence of Integers present in any given ArrayList.
您可以使用以下算法获取任何给定 ArrayList 中存在的最大整数序列。
- Add all the Integers of the List to a Set.
- Iterate over the Set.
- Check for the element if (element - 1) is present in the Set. If yes, continue to the next iteration because it is not the start of the sequence.
- Else, in a while loop check how many elements in succession to the element are present in the Set.
- 将列表的所有整数添加到集合中。
- 迭代集合。
- 如果 (element - 1) 存在于集合中，则检查元素。如果是，继续下一次迭代，因为它不是序列的开始。
- 否则，在 while 循环中检查 Set 中存在多少个元素的连续元素。
A sample program for the mention algo will look like:
提及算法的示例程序如下所示：
package org.practice.algorithms.arrays;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class LargestSequence {
public Integer[] getLargestSequence(Integer[] numberArray) {
List<Integer> largestSequence = new ArrayList<Integer>();
int largestSequenceCount = 0;
Set<Integer> numbersSet = getSetFromArray(numberArray);
for (Integer integer : numbersSet) {
if(numbersSet.contains(integer -1)) {
//this number is not the start of the sequence.
continue;
} else {
int count = 0;
List<Integer> largestSequenceTemp = new ArrayList<Integer>();
while(numbersSet.contains(integer)) {
largestSequenceTemp.add(integer);
integer++;
count++;
}
if(count > largestSequenceCount) {
largestSequenceCount = count;
largestSequence = largestSequenceTemp;
}
}
}
return largestSequence.toArray(new Integer[largestSequence.size()]);
}
private Set<Integer> getSetFromArray(Integer[] numberArray) {
Set<Integer> numbersSet = new HashSet<Integer>();
if(null != numberArray && numberArray.length > 0) {
for (int number : numberArray) {
numbersSet.add(number);
}
}
return numbersSet;
}
}
