java - 获取二维整数数组中最长的序列

Question

我被这个问题困扰有一段时间了。目标是返回最长重复序列的 Arraylist。如果我有

int[][] a = {{ 1, 1, 3, 4 }
             { 2, 2, 2, 1}
             { 3, 3, 3, 3}
             { 0, 0, 1, 1}};

方法longestSequence()应该返回一个[3,3,3,3]的Arraylist，因为3具有最长的序列。我必须只水平找到序列。请 smb 告诉我我做错了什么吗？

   int[][] a = {{ 1, 1, 3, 4 }
                 { 2, 2, 2, 1}
                 { 3, 3, 3, 3}
                 { 0, 0, 1, 1}};

    public List<Integer> longestSequence(int[][]a){
       int count = 1, max = 1;
       List<Integer> list = new ArrayList<Integer>();

       for (int i = 0; i < a.length; i++)
          for(int j = 1; j < a[i].length; j++) {
             if (a[i][j] >= a[i][j-1]) {
                count++;
                list.add(a[i][j]);
             }  else {
                   if (count > max) {
                   max = count;
               }
            list.clear();
            count = 1;
        }
    }

    return list;
}

Answer 1

问题似乎是您没有正确清除列表，并且没有保留最佳列表作为要返回的值。

您可以保留一个maxList，即与长度max相对应的元素列表:

max = count; maxList = new ArrayList<>(list);

不要简单地使用 maxList = list，因为它会被 list.clear() 调用清除。

或者，保留最长序列中元素的值(例如 3)，然后在长度 max 的末尾构造一个列表，其中所有元素都是例如 3。 3.

int bestValue = -1;
int bestLength = 0;
for (int i = 0; i < a.length; ++i) {
  int[] row = a[i];
  int j = 0;
  while (j < row.length) {
    int start = j++;
    while (j < row.length && row[j] == row[start]) j++;
    if (j-start > bestLength) {
      bestLength = j - start;
      bestValue = row[start];
    }
  }
}
return Collections.nCopies(bestLength, bestValue);