Как улучшить алгоритм для Max Common Array Slice?

Question

Меня попросили пройти тест кода HackerRank, и задание, которое я попросил, - это Max Common Array Slice. Проблема заключается в следующем:

Вам предоставляется последовательность из n целых чисел a0, a1,. , , , an-1 и задача состоит в том, чтобы найти максимальный срез массива, который содержит не более , чем два разных числа.

Вход 1:

[1, 1, 1, 2, 2, 2, 1, 1, 2, 2, 6, 2, 1, 8]

Результат 1: Ответ 10 потому что срез массива (0, 9) является самым большим фрагментом массива с не более чем двумя разными числами.

• В этом фрагменте 10 предметов, которые являются «1, 1, 1, 2, 2, 2, 1, 1, 2, 2».
• 2 разные числа для этого среза равны 1 и 2.

вход 2:

[53, 800, 0, 0, 0, 356, 8988, 1, 1]

Результат 2: Ответ равен 4, потому что срез (1, 4) является наибольшим фрагментом массива с не более чем двумя разными числами. Срез (2, 5) также будет действительным, и будет по-прежнему дает результат 4.

• Есть 4 элементов в этом срезе, которые являются «800,0,0,0».
• 2 разных числа для этого среза являются 800 и 0.

Максимального срез общего массива массива, который содержит реализацию не более два различных номера в Java принимает запятые массива чисел из STDIN и вывод записывается обратно в консоль.

Реализация, которую я предоставляю (ниже), работает, однако 3 тайм-аута контрольных случаев в HR. Очевидно, что HR скрывает тестовые примеры, поэтому я не смог точно определить условия, в которых был установлен тайм-аут, или даже продолжительность таймаута. Я не удивлен таймаутом, хотя, учитывая асимптотическую сложность моего решения. Но мой вопрос: как можно улучшить мое решение?

Заранее благодарим всех, кто поможет!

import java.io.*; 
import java.lang.*; 
import java.util.*; 
import java.util.stream.*; 

public class Solution { 
    public static void main(String args[]) throws Exception { 
     BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
     String line = br.readLine(); 
     List<Integer> inputSequence = parseIntegerSequence(line); 
     int largestSliceSize = calculateLargestSlice(inputSequence); 

     System.out.println(largestSliceSize); 
    } 

    private static List<Integer> parseIntegerSequence(String input) { 
     if (input == null) 
      return new ArrayList(); 

     return Arrays.asList(input.split("\\s*,\\s*")) 
       .stream() 
       .filter(item -> item.matches("^\\s*-?[0-9]+\\s*$")) 
       .map(item -> Integer.parseInt(item)) 
       .collect(Collectors.toList()); 
    } 

    private static int calculateLargestSlice(List<Integer> inputSequence) { 

     Map<Integer, Integer> temporaryMap = new HashMap<>(); 

     int result = 0; 
     int startIndex = 0; 
     int uniqueItemCount = 0; 

     Integer[] array = inputSequence.toArray(new Integer[inputSequence.size()]); 

     while (startIndex < array.length) { // loop over the entire input sequence 
      temporaryMap.put(array[startIndex], startIndex); 
      uniqueItemCount++; 

      for (int j = startIndex + 1; j < array.length; j++) { 
       if (temporaryMap.get(array[j]) == null) { 
        if (uniqueItemCount != 2) { 
         temporaryMap.put(array[j], j); 

         uniqueItemCount++; 
         if (j == array.length - 1) { 
          result = Math.max(result, j - startIndex + 1); 
          startIndex = array.length; 
          break; 
         } 
        } else { 
         result = Math.max(result, j - startIndex); 
         int item = array[j-1]; 
         int firstFoundIndex = 0; 
         for(int k=j-1; k>=0; k--) 
         { 
          if(array[k] != item) 
          { 
           firstFoundIndex = k+1; 
           break; 
          } 
         } 
         startIndex = firstFoundIndex; 
         temporaryMap.clear(); 
         uniqueItemCount = 0; 
         break; 
        } 
       } else if (temporaryMap.get(array[j]) != null) { 
        if (j == array.length - 1) { 
         result = Math.max(result, j - startIndex + 1); 
         startIndex = array.length; 
         break; 
        } 
       } 
      } 
     } 
     return result; 
    } 
} 

Answer 1

Это питон решение, в соответствии с просьбы ОП

def solution(arr): 
    if (len(arr) <= 2): print arr 
    lres = 0 
    rres = 0 
    l = 0 
    r = 1 
    last = arr[1] 
    prev = arr[0] 
    while(r <= len(arr)-1): 
     if prev != last: 
      if arr[r] == prev: 
       prev = last 
       last = arr[r]    
      elif arr[r] != last: 
       l = r-1 
       while(arr[l-1] == last): 
        l -= 1 
       last = arr[r] 
       prev = arr[r-1]    
     else: 
      if arr[r] != prev: 
       last = arr[r] 
     if r - l > rres-lres: 
      rres = r 
      lres = l 
     r += 1 
    print arr[lres:rres+1] 

Для текущего сегмента допустят, что last добавляется последнее значение и prev является вторым отчетливым значением в сегменте. (изначально они могут быть равными).

Давайте укажем указатели l и r на левый и правый концы текущего сегмента с не более чем двумя отдельными элементами. И, допустим, рассмотрим элемент arr[r]. Если текущий сегмент [l,r-1] содержит только один отличный элемент, мы можем смело добавить arr[r], возможно, обновить last и prev. Теперь, если arr[r] равно last, тогда нам ничего не нужно. Если arr[r] равно prev, нам необходимо обменять prev и last. Если он не соответствует ни одному из этих двух, нам нужно обновить левый указатель l, проследив его от r-1 до тех пор, пока мы не найдем элемент, который не равен last, а затем обновим last и prev.

Answer 2

Это мой ответ на Java, и он прошел все тестовые примеры HackerRank. Пожалуйста, не стесняйтесь комментировать, если вы найдете что-то не так.

public static int maxCommonArraySlice(List<Integer> inputSequence) { 
    if(inputSequence.size() < 2) return inputSequence.size(); // I'm doubting this line should be <= 2 

    List<Integer> twoInts = new LinkedList<>(); 
    twoInts.add(inputSequence.get(0)); 
    int start = 0; 
    int end = inputSequence.size(); 
    int count = 0; 
    int max_length = 0; 

    while(start < end) { 
     if(twoInts.contains(inputSequence.get(start))) { 
      count++; 
      start++; 
     } 
     else if(twoInts.size() == 1) { 
       twoInts.add(inputSequence.get(start)); 
     } 
     else { // twoInts.size() is 2 
       count = 0; 
       start--; 
       twoInts.set(0, inputSequence.get(start)); 
       twoInts.set(1, inputSequence.get(start + 1)); 
     } 

     if(count > max_length) { 
      max_length = count; 
     } 
    } 
    return max_length; 

} 

public static void main(String[] args) { 

    List<Integer> input = new LinkedList<Integer>(Arrays.asList(53,800,0,0,0,356,8988,1,1)); 
    System.out.println(maxCommonArraySlice(input)); 

}