Испытательные корпуса не могут удовлетворить

Question

Я всего лишь новичок. Я столкнулся с этим вопросом, для которого мой код не удовлетворяет всем/большинству тестовых случаев.

Вопрос:

Дан массив чисел, найти количество непустых подмассивов, в которых минимальный и максимальный элемент идентичны.

Пример:

Входной сигнал: Array = [1, 1, 3]

Выход: 4

Пояснение:

Необходимая суб- массивы [1], [1], [3], [1,1]

Мое решение:

Сортировка массива и решить эту проблему.

Код:

for(int i = 0; i < testCases; i++){ 
     int arraySize = in.nextInt(); 
     int array[] = new int[arraySize]; 
     for(int j = 0; j < arraySize; j++){ 
      array[j] = in.nextInt(); 
     } 
     temp[i] = (findSubArrays(array)); 
} 
for(int i = 0; i < testCases; i++){ 
     System.out.println(temp[i]); 
} 

private static int findSubArrays(int[] array) { 
    Arrays.sort(array); 

    //Since each element can form a sub-array of its own 
    int noOfSubArrays = array.length; 

    for(int i = 0; i < array.length-1; i++){ 
     if(array[i] == array[i+1]){ 
      noOfSubArrays++; 
     } 
    } 
    return noOfSubArrays; 
} 

Answer 1

Так вы сортировка массива, чтобы начать точки и конечные точки соседних, так что вам не нужен вложенный обход. В этом есть смысл. Проблема в том, что вы подсчитываете соседние дубликаты, но то, что вам действительно нужно, это T(n) или номер треугольника последовательных дубликатов. Рассмотрим простой сценарий:

[1, 1, 1] 

Ваш алгоритм возвращает 5, но есть на самом деле 6 подмножеств (по начало & конечного индекса):

0, 0 
0, 1 
0, 2 
1, 1 
1, 2 
2, 2 

Так давайте обновим алгоритм для вычисления треугольника числа каждого последовательность:

private static int findSubArrays(int... array) { 
    Arrays.sort(array); 

    int sequenceCount = 0; 
    int total = 0; 
    for (int i = 0; i < array.length + 1; i++) { 
     if (i == array.length || (i > 0 && array[i] != array[i - 1])) { 
      total += triangle(sequenceCount); 
      sequenceCount = 0; 
     } 
     sequenceCount++; 
    } 
    return total; 
} 

private static int triangle(int n) { 
    return (n * (n + 1))/2; 
} 

Теперь вызова findSubArrays(1, 1, 1) возвращается 6 и findSubArrays(1, 1, 3) возвращает 4.