Блог

Учитывая отсортированный массив, например [1,2,4,4,4] . Каждый элемент в массиве должен встречаться ровно столько же раз, сколько и элемент. Например, 1 должно произойти 1 раз, 2 должно произойти 2 раза, n должно произойти n раз, После минимального количества ходов массив будет отображаться как [1,4,4,4,4]

 Original                          Shifted                   Min Moves       Reason
[1,2,4,4,4]                       [1,4,4,4,4]               2               delete 2 and insert 4
[1, 1, 3, 4, 4, 4]                [1,4,4,4,4]               3               delete 1,3 an insert 4
[10, 10, 10]                      []                        3               delete all 10s
[1, 1, 1, 1, 3, 3, 4, 4, 4, 4, 4] [1, 3, 3, 3, 4, 4, 4, 4]  5               delete 1,1,1,4 and insert 3
 

Нам разрешено полностью удалять/удалять некоторые элементы, как описано выше.

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

 public static int minMoves(int[] data) {
    Map<Integer, Integer> dataMap = new HashMap<>();
    for(int i=0; i<data.length;i  ) {
        if(dataMap.containsKey(data[i])) {
            dataMap.put(data[i], dataMap.get(data[i]) 1);
        }else {
            dataMap.put(data[i], 1);
        }
    }
    
    System.out.println("Map - " dataMap);
    
    int[] minOperations = {0};      
    dataMap.forEach((digit,frequency)->{            
        if(digit!=frequency) {
            if(digit<frequency) {
                minOperations[0]  = (frequency-digit);
            }else if(digit>frequency amp;amp; (digit-frequency)<=minOperations[0]) {
                minOperations[0]  = digit-frequency;
            }else {
                minOperations[0]  = frequency;
            }   
        }                               
        System.out.println(digit "  " frequency "  " minOperations[0]);
    });     
    return minOperations[0];
}
 

Приведенная выше логика прекрасно работает в вышеуказанных случаях. Но в некоторых случаях это не удается.

 Failed Case - [1, 2, 2, 2, 5, 5, 5, 8] should return 4, But it's returning 5.
 

Я чувствую, что у моего решения мало проблем

1. Не оптимистично/Менее результативно
2. Неудача в крайних случаях
3. Не следуя никакому алгоритмическому подходу

Пожалуйста, помогите указать. Каковы правильные подходы/алгоритмы, доступные для более эффективного решения этой проблемы.

Дополнительные Объяснения:

Существует массив A из N целых чисел, отсортированных в неубывающем порядке. За один ход вы можете либо удалить целое число из A, либо вставить целое число до или после любого элемента A. Цель состоит в том, чтобы создать массив, в котором все значения X, присутствующие в массиве, встречаются ровно X раз.

Учитывая = [1, 2, 2, 2, 5, 5, 5, 8], ваша функция должна повториться 4. Вы можете удалить 8 и одно вхождение 2 и вставить 5 дважды, в результате чего [1, 2, 2, 5, 5, 5, 5, 5] после четырех ходов. Обратите внимание, что после удаления в массиве больше не встречается 8.

для данного массива A пересчитывает минимальное количество ходов, после которого каждое значение X в массиве повторяется ровно X раз. Обратите внимание, что при необходимости допускается полное удаление некоторых значений.

Каково минимальное количество ходов, после которых каждое значение X в массиве встречается ровно X раз?

Ошибка заключается в этом сравнении:

 (digit-frequency)<=minOperations[0]
 

Нет никакой логики в сравнении с промежуточной, текущей суммой minOperations[0] . Он должен сравнить следующие два:

• Сколько операций вставки необходимо, чтобы получить необходимое количество цифр-это левая сторона сравнения (ОК)
• Сколько операций удаления необходимо для удаления всех этих цифр, это frequency

Так что это сравнение должно быть:

 digit - frequency <= frequency
 

Некоторые другие замечания:

• Как вы говорите, входные данные отсортированы, нет необходимости создавать карту. Вы можете сразу же подсчитать количество цифр при повторении слева направо по массиву и одновременно обновить minOperations его .
• Нет необходимости создавать minOperations массив. Это может быть просто примитивом.
• Количество проверяемых выражений можно немного уменьшить, используя abs и min

Вот как вы могли бы обновить свой код:

 import java.lang.Math.*;

// ...

public static int minMoves(int[] data) {
    int minOperations = 0;
    for(int i = 0, j = 0; i < data.length; i = j) {
        while (j < data.length amp;amp; data[i] == data[j]) j  ;
        int frequency = j - i;
        minOperations  = Math.min(Math.abs(data[i] - frequency), frequency);
    }
    return minOperations;
}
 

Попробуй это :

 public static int minMovements(Integer[] array) {
    int numberOfMoves = 0;
    List<Integer> arrayList = List.of(array);
    List<Integer> uniques = arrayList.stream().distinct().collect(Collectors.toList());

    for (Integer e : uniques) {
      int ocurrences = (int) arrayList.stream().filter(o -> o == e).count();
      numberOfMoves  = Integer.min(Math.abs(e - ocurrences), ocurrences);
    }
    return numberOfMoves;
  }