最小移动以转换列表，使每个元素等于其自己的频率

Question

给定一个像 [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

我们完全可以 delete/drop 某些元素，如上所述。

我需要找到获得转换版本所需的最小 rotations/moves 数量。所以，我写了下面的逻辑来找到原始数组所需的最小移动次数。

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 && (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.

I feel my solution has few problems

Not optimistic/Less performant

Failing on edge cases

Not following any algorithmic approach

请大家帮忙指出。什么是正确的 approaches/algorithms 可以更有效地解决这个问题。

更多说明：

有一个非降序排列的N个整数数组A。只需一步，您就可以删除来自A的整数或在A的任何元素之前或之后插入一个整数。目标是实现一个数组其中数组中存在的所有值 X 正好出现 X 次。

Given A = [1, 2, 2, 2, 5, 5, 5, 8], your function should retum 4. You can delete the 8 and one occurrence of 2, and insert 5 twice, resulting in [1, 2, 2, 5, 5, 5, 5, 5] after four moves. Notice that after the removals, there is no occurrence of 8 in the array anymore.

给定一个数组 A 返回数组中每个值 X 之后的最小移动次数恰好发生 X 次。请注意，如果合适，可以完全删除某些值。

数组中的每个值 X 恰好出现 X 次后最少移动多少次？

Answer 1

这个比较的错误是：

(digit-frequency)<=minOperations[0]

和中间比较没有逻辑，运行和minOperations[0]。它应该比较以下两个：

需要多少次insert操作才能达到要求的位数--这是左边的比较(OK)
需要多少次delete操作才能把这些数字都去掉，这是frequency

所以比较应该是：

digit - frequency <= frequency

一些其他备注：

正如你所说的输入是排序的，不需要创建Map。您可以在从左到右遍历数组时立即计算位数，并同时更新 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 && data[i] == data[j]) j++;
        int frequency = j - i;
        minOperations += Math.min(Math.abs(data[i] - frequency), frequency);
    }
    return minOperations;
}

Answer 2

试试这个：

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

Answer 3

private static void findMinMoves(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);
        }
    }
    int[] minOperations = {0};
    dataMap.forEach((digit, occurrence) -> {
        if (digit != occurrence) {
            if (digit < occurrence) {
                minOperations[0] += (occurrence - digit);
            } else if (digit > occurrence) {
                minOperations[0] += Math.min(Math.abs(occurrence - digit), occurrence);
            } else {
                minOperations[0] += occurrence;
            }
        }
    });
    System.out.println("Minimum occurrences" + minOperations[0]);
}

时间复杂度：O(n) Space 复杂度：O(n)

最小移动以转换列表，使每个元素等于其自己的频率

Minimum moves to transform a list so that each element equals its own frequency

arrays

sorting

algorithm

math

data-structures