Самый длинный subArray с не более чем двумя различными значениями, которые отличаются не более чем на 1 - PullRequest
Новая
       35

Самый длинный subArray с не более чем двумя различными значениями, которые отличаются не более чем на 1

1 голос
/ 03 мая 2020

Учитывая массив целых чисел, какова длина самого длинного subArray, содержащего не более двух различных значений, так что различные значения отличаются не более чем на 1

Например:

обр = [0, 1, 2, 1, 2, 3] -> длина = 4; [1,2,1,2]

arr = [1, 2, 3, 4, 5] -> длина = 2; [1,2]

arr = [1, 1, 1, 3, 3, 2, 2] -> длина = 4; [3,3,2,2]

У меня есть такой код 

 public static int longestSubarray(List<Integer> arr) {
        int max = 0;
        Set<Integer> set = new HashSet<>();
        int i = 0;
        int j = 1;
        while (i < arr.size() - 1) {
            set.add(arr.get(i));
            while (j < arr.size() && Math.abs(arr.get(i) - arr.get(j)) < 2) {
                if (!set.contains(arr.get(j))) {
                    if (set.size() == 2) {
                        break;
                    } else {
                        set.add(arr.get(j));
                    }
                }
                ++j;
            }
            max = Math.max(max, j - i);
            j = ++i + 1;
            set.clear();
        }
        return max;
    }

Может ли быть лучшее решение?

1 Ответ

0 голосов
/ 03 мая 2020

Да. Вот динамическая c программа с O(n) временем и O(1) пробелом. Идея состоит в том, что мы можем получить ответ для последовательности, заканчивающейся на A[i], посмотрев на лучшую последовательность, заканчивающуюся на A[i-1], которая, возможно, включает в себя более высокие элементы, и лучшую последовательность, заканчивающуюся на A[i-1], которая, возможно, включает в себя более низкие элементы.

JavaScript код: 

function f(A){
  if (A.length < 2)
    return A.length;
    
  let best = 1;
  let bestLower = 1;
  let bestHigher = 1;
  
  for (let i=1; i<A.length; i++){
    if (A[i] == A[i-1]){
      bestLower = bestLower + 1;
      bestHigher = bestHigher + 1;
    
    } else if (A[i] - 1 == A[i-1]){
      bestLower = 1 + bestHigher;
      bestHigher = 1;
    
    } else if (A[i] + 1 == A[i-1]){
      bestHigher = 1 + bestLower;
      bestLower = 1;
    
    } else {
      bestLower = 1;
      bestHigher = 1;
    }

    best = Math.max(best, bestLower, bestHigher);
  }
  
  return best;
}

arrays = [
  [0, 1, 2, 1, 2, 3], // length = 4; [1,2,1,2]
  [1, 2, 3, 4, 5], // length = 2; [1,2]
  [1, 1, 1, 3, 3, 2, 2] // length = 4; [3,3,2,2]
];

for (let arr of arrays){
  console.log(JSON.stringify(arr));
  console.log(f(arr));
}
...