Max Common Array Sliceのアルゴリズムを改善するには？

Question

私はHackerRankコードテストを受けるように頼まれ、私に求められたエクササイズはMax Common Array Sliceです。問題は次のようになります。

n個の整数a0、a1 ,. 。 。 、an-1および タスクは、2つの異なる数よりも多くの文字が含まれていない配列の最大スライスを見つけることです。

入力1：

[1、1、1、2、2、2、1、1、2、2、6、2、1、8]

結果1：回答10なぜなら（0,9）の配列スライスは2つ以上の異なる数を持つ配列の最大スライスである であるからです。

• このスライスには、「1,1,1,2,2,2,1,2,2」という10の項目があります。このスライスの
• 2つの異なる番号が1であり、2

入力2：

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

結果2：（1,4）のスライスが2つ以下の異なる数を持つ配列の最大スライス であるため、答えは4です。スライス（2、5） も有効だろうと、まだ「800,0,0,0」です。このスライス内の4つの項目があります。4.

• の結果を与えるだろう。このスライスの
• 2つの異なる番号がJavaでない以上 二つの異なる数の実装が含まれている配列の最大共通配列スライスはコンマSTDINから数値の 配列を区切らとる

800及び0です。出力はコンソールに書き戻されます。

実装方法は以下のとおりですが、HRでは3つのテストケースがタイムアウトします。明らかに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

現在のセグメントについてOP

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セグメントにおける第二の別個の値であるものとする、Pythonの溶液です。 （当初は同じかもしれない）。

現在のセグメントの左端と右端に最大で2つの異なる要素を持つポインタlとrを用意しましょう。要素arr[r]を考えてみましょう。 現在のセグメント[l,r-1]に個別の要素が1つしか含まれていない場合は、arr[r]を安全に追加し、lastとprevを更新することができます。 arr[r]がlastに等しい場合は、何もする必要はありません。 arr[r]がprevに等しい場合は、prevとlastを交換する必要があります。それらの2つのどちらにも等しくない場合は、と等しくない要素が見つかるまでr-1から戻ってlastとprevを更新するまで、lを左ポインタに更新する必要があります。

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)); 

}