Блог

У меня есть массив чисел, скажем arr=[3,4,2,3,1] . Здесь индекс arr представляет число, а arr[index] частота этого числа. Для примера arr мы имеем

 1 three times
2 four times
3 two times
4 three times
5 one time
  

Пара может состоять из двух чисел, так что их абсолютная разница равна либо 0, либо 1.
Нам нужно найти максимально возможные пары. Число не может использоваться чаще, чем его заданная частота. Для примера arr пары могут быть:
(1,1),(2,2),(2,2),(3,3),(4,4),(4,5)
Таким образом, 6 является ответом.
Примечание: здесь у нас остается дополнительный 1, но это не имеет значения.

Мой подход:
Вычислите mod 2 для каждого числа и получите массив из 0 и 1 и для каждого количества обновлений частоты count = arr[i]/2 . Итак, для примера arr я останусь с: [1,0,0,1,1]
Теперь, если я увижу любые два последовательных обновления 1, количество обновлений на 1

Он работал для выборочных тестовых примеров, но не удался в скрытых тестовых примерах. Кто-нибудь может помочь мне понять, что не так с моей идеей?

Неудачный случай:
[34,2,435,45,57,6,8,3,57,235]
Мой результат: 440
Ожидаемый результат: 441

Логика, лежащая в основе

примите arr [i]/2 в счет, и если нечетным является элемент, возьмите один в качестве переноса для следующего

       public static void main(String args[]) {
                int[] arr=new int[]{34,2,435,45,57,6,8,3,57,235};
                int len=arr.length;
                int count=0,prev=0;
                if(arr[0]%2!=0)prev=1;
                count =arr[0]/2;
                for(int i=1;i<len;i  ){
                    if(prev==1){
                       arr[i]--;
                       count  ;
                    }
                    if(arr[i]%2!=0)prev=1;
                    else prev=0;
                    count =arr[i]/2;
                    
                }
        
              System.out.println(count);
        }
  

Временная сложность равна O (n), а пространство равно O (1)

Обратите внимание, что при вашем подходе вы не используете последний из 57.

Но вы можете соединить это с одним из 6, другой из 6 будет соединен с 8, 8 будет соединен с 3, а 57 с 235 — так что все элементы работают.

Вам нужно выбирать на каждом шаге: что лучше — оставить последнюю свободную или создать пару со следующим значением.