import java.util.Arrays;
import static java.lang.System.out;
class TestCase{
int[] test;
int answer;
TestCase(int[] test,int answer){
this.test = test;
this.answer = answer;
}
}
public class Solution {
public static void main(String[] args) {
TestCase[] tests = {
new TestCase(new int[]{2, 3, 4, 3, 2, 2, 4},3),
new TestCase(new int[]{2, 3, 3, 3, 3, 4, 3, 3, 2, 2, 4},7),
new TestCase(new int[]{1,2,3,3,4,2,3,2,3,2,2,2,1,3,4},7),
new TestCase(new int[]{2, 7, 8, 7, 8, 7},5),
new TestCase(new int[]{-1,2,2,2,2,2,2,2,2,2,2,-1,-1,4},13),
new TestCase(new int[]{1,2,3,4,5,6,7,7},3),
new TestCase(new int[]{0,0,0,0,0},0),
new TestCase(new int[]{0,0,0,2,2,2,1,1,1,1},7),
new TestCase(new int[]{},0)
};
for(int i=0;i<tests.length;++i){
int ans = maxContiguousArrayWith2UniqueElements(tests[i].test);
out.println(Arrays.toString(tests[i].test));
out.println("Expected: " + tests[i].answer);
out.println("Returned: " + ans);
out.println("Result: " + (tests[i].answer == ans ? "ok" : "not ok"));
out.println();
}
}
private static int maxContiguousArrayWith2UniqueElements(int[] A){
if(A == null || A.length <= 1) return 0;
int max_subarray = 0;
int first_number = A[0],second_number = A[0];
int start_index = 0,same_element_run_length = 1;
for(int i=1;i<A.length;++i){
if(A[i] != A[i-1]){
if(first_number == second_number){
second_number = A[i];
}else{
if(A[i] != first_number && A[i] != second_number){
max_subarray = Math.max(max_subarray,i - start_index);
start_index = i - same_element_run_length;
first_number = A[i-1];
second_number = A[i];
}
}
same_element_run_length = 1;
}else{
same_element_run_length++;
}
}
return first_number == second_number ? max_subarray : Math.max(max_subarray,A.length - start_index);
}
}
ВЫВОД:
[2, 3, 4, 3, 2, 2, 4]
Expected: 3
Returned: 3
Result: ok
[2, 3, 3, 3, 3, 4, 3, 3, 2, 2, 4]
Expected: 7
Returned: 7
Result: ok
[1, 2, 3, 3, 4, 2, 3, 2, 3, 2, 2, 2, 1, 3, 4]
Expected: 7
Returned: 7
Result: ok
[2, 7, 8, 7, 8, 7]
Expected: 5
Returned: 5
Result: ok
[-1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, -1, -1, 4]
Expected: 13
Returned: 13
Result: ok
[1, 2, 3, 4, 5, 6, 7, 7]
Expected: 3
Returned: 3
Result: ok
[0, 0, 0, 0, 0]
Expected: 0
Returned: 0
Result: ok
[0, 0, 0, 2, 2, 2, 1, 1, 1, 1]
Expected: 7
Returned: 7
Result: ok
[]
Expected: 0
Returned: 0
Result: ok
Алгоритм:
- Итак, мы поддерживаем 2 переменные first_number и second_number , которые будут содержать эти 2 уникальных числа.
- Как вы знаете, может быть много возможных подмассивов, которые мы должны рассмотреть, чтобы получить максимальную длину подмассива, которая имеет 2 уникальных элемента. Следовательно, нам нужна переменная-указатель, которая будет указывать на начало подмассива. В этом случае указатель start_index .
- Любой подмассив разрывается, когда мы находим третье число, которое не равно first_number или second_number . Итак, теперь мы вычислим предыдущую длину подмассива (в которой были эти 2 уникальных элемента), выполнив i - start_index .
- Сложная часть этого вопроса - как получить start_index следующего подмассива.
- Если вы внимательно наблюдаете, second_number предыдущего подмассива становится first_number текущего подмассива и третий номер, с которым мы только что столкнулись, становится second_number этого текущего подмассива.
- Итак, один способ вычислить, когда first_number запущен, - запустить цикл while в обратном направлении, чтобы получить start_index . Но это сделало бы алгоритм O (n ^ 2) , если нужно рассмотреть много подмассивов (что будет).
- Следовательно, мы поддерживаем переменную с именем same_element_run_length , которая просто отслеживает длину или частоту повторения числа и обновляется всякий раз, когда оно прерывается. Итак, start_index для следующего подмассива после того, как мы встретим третий номер, становится start_index = i - same_element_run_length .
- Остальные вычисления не требуют пояснений.
- Сложность времени: O (n) , Сложность пространства: O (1) .