【每日阅读】2020年6月14日-转变数组后最接近目标值的数组和

链接

https://leetcode-cn.com/problems/sum-of-mutated-array-closest-to-target/

文章截图

简评

今天做了一道算法题,以前遇到这种没有思路的算法题我肯定是看答案的,但是今天没有,就是因为前些天我看的这篇文章,那篇文章给我的启示就是“先给出解决方案,再谈优化”。今天这道算法题我就是这样,把头脑中的模糊想法一步步具象化成代码思路,最后实现(没有进一步优化)。即使这个思路很暴力,很没有“算法”的感觉。我也发了解题思路,有兴趣的话看这里。题解截图见下方

代码:

class Solution {
    public int findBestValue(int[] arr, int target) {
        int allSum = 0;
        int max = 0;
        for (int value : arr) {
            allSum += value;

            if (max < value) {
                max = value;
            }
        }

        int allAverage = target / arr.length;

        if (allSum <= target) {
            return max;
        } else {
            // 小于平均数的数字之和
            int lowerAverageSum = 0;
            // 大于平均数的应该有的总和
            int higherAverageSum = target;
            // 大于平均数的数字个数
            int higherCount = 0;
            for (int value : arr) {
                if (value <= allAverage) {
                    lowerAverageSum += value;
                    higherAverageSum -= value;
                } else {
                    higherCount++;
                }
            }

            // 向下取整的答案
            int downResult = higherAverageSum / higherCount;
            // 向上取整的答案
            int upResult = downResult + 1;

            int[] newArr = new int[higherCount];

            boolean shouldContinue = false;
            int i = 0;
            for (int value : arr) {
                // 如果还有比downResult小的数,那需要递归的把大于平均值的数再做一遍计算
                if (value > allAverage && value < downResult) {
                    shouldContinue = true;
                }

                if (value > allAverage) {
                    newArr[i++] = value;
                }
            }

            if (shouldContinue) {
                return findBestValue(newArr, higherAverageSum);
            }

            // 和target的差
            int downDiff = target - (lowerAverageSum + downResult * higherCount);
            int upDiff = (lowerAverageSum + upResult * higherCount) - target;

            // 取差小的
            if (downDiff <= upDiff) {
                return downResult;
            } else {
                return upResult;
            }
        }
    }
}

原创文章,作者:geekgao,如若转载,请注明出处:https://www.geekgao.cn/archives/1933

发表评论

电子邮件地址不会被公开。 必填项已用*标注

GitLab GitHub
分享本页
返回顶部