光与影的个人博客

NEUCoder

0%

lc517.超级洗衣机

发表于 更新于 分类于 ，

517. 超级洗衣机

贪心的思路并不难，就是太难想到了

思路1：邻居平分法（我自己的思路）

类似于最优解的区域法，针对每个洗衣机，将整个数组划分为左边右边两个子区域，计算左右两个区域的衣服总和，并定会存在总数小于或者大于 平均*区域数量 的区域，如果当前洗衣机衣服多，就将多余的衣服分给缺衣服的区域（给了邻居）

  1. 每遍历一次所有洗衣机等价于一次移动
  2. 最后一次遍历所有情况下划分的子区域，均满足 平均*区域数量 的性质

复杂度分析：

  1. 时间复杂度：每次平均都需要从头到尾遍历数组，共需要遍历结果次数的数组，时间复杂度为O(KN)
  2. 空间复杂度：额外开辟了一个存储前缀和的数组，空间复杂度为O(N)

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public int findMinMoves(int[] machines) {
        int result = 0;
        int average;
        int numOFMach = machines.length;
        int[] preSum = new int[numOFMach];
        preSum[0] = machines[0];
        for(int i = 1;i < numOFMach;i++){
            preSum[i] = preSum[i - 1] + machines[i];
        }
        //判断是否可分
        if(preSum[numOFMach - 1] % numOFMach != 0){
            return -1;
        }
        average = preSum[numOFMach - 1] / numOFMach;
        boolean flag;
        while(true){
            flag = true;
            for(int i = 0;i < numOFMach;i++){
                //如果左边区域小，往左边区域移动
                if(machines[i] > 0){
                    if(i != 0 && preSum[i] - machines[i] < i * average){
                        machines[i] -= 1;
                        machines[i - 1] += 1;
                        preSum[i - 1] += 1;
                        flag = false;
                    }
                    else if(i != numOFMach - 1 && preSum[numOFMach - 1] - preSum[i] < (numOFMach - i - 1) * average){
                        machines[i] -= 1;
                        machines[i + 1] += 1;
                        preSum[i] -= 1;
                        flag = false;
                    }
                }
            }
            //没有平均操作就返回
            if(flag){
                return result;
            }
            result++;
        }
    }

  • 可惜差两个测试用例，超时

思路2：官方题解

基于区域的最优，主要是三个点

  1. 如果将数组划分为前后两个区域，如果是一个多衣服，一个少衣服，要达到平均状态最少也要将

    多衣服的区域多的衣服，转移到少衣服区域，也就是 最少的次数至少也是多衣服区域多出来的衣服

  2. 单个区域内要达到平均，最多衣服的洗衣机，要转移成平均，意味着 最少的次数至少是最多衣服数量洗衣机转移的衣服数量

  3. 这种转移可以并行进行，也就得到了最终的贪心策略-寻找多最多的区域或者某个洗衣机

复杂度分析：

  1. 时间复杂度：只需要遍历一次数组计算上面两个状态，时间复杂度为O(N)
  2. 空间复杂度：不需要额外空间，空间复杂度为O(1)

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int findMinMoves(int[] machines) {
    //首先求和计算平均值
    int result = 0;
    int sum = 0;
    int average;
    for(int i = 0;i < machines.length;i++){
        sum += machines[i];
    }
    if(sum % machines.length != 0){
        return -1;
    }
    //计算平均数，并用sum作为前i个元素所需要移入或移出的个数
    average = sum / machines.length;
    sum = 0;
    int tempNeed;
    for(int i = 0;i < machines.length;i++){
        tempNeed = machines[i] - average;
        sum += tempNeed;
        result = Math.max(Math.abs(sum),Math.max(tempNeed, result));
    }
    return result;
}