狗家电面

面试官迟到了15分钟orz…不废话,直接做题,只有一道题

题目:给一个数组,里面是员工的工资,工资总额有一个budget,一开始员工工资总和是超过budget的,要求求出数k,然后把数组里所有比k大的工资都减少到k,使得数组里的工资总和刚好等于budget。举个例子,工资数组:[100,200,300,400],budget=800,那么求出的k应该是250, 这样削减后的工资是100 + 200 + 250 + 250刚好等于800

补充内容 (2018-11-10 15:35):
数组没有排序

不知道这样对吗,O(n)

public static long findK(int[] salary, int budget) {
        int n = salary.length;
        int sum = 0;
        Arrays.sort(salary);
        int[] sums = new int[salary.length];
        for (int i = 1; i < n; i++) {
            sum += salary[i - 1];

            int rest = budget - sum;
            long expect = rest / (n - i);
            if (salary[i] > expect) {
                return expect;
            }
        }

        return 0;
    }

补充内容 (2018-11-10 14:34):
如果工资没排序的话 就O(nlogn)

这个666字数字数

补充内容 (2018-11-10 16:41):
要考虑一下这种情况:[100, 200, 300, 400], budget = 40。

应该是binary search就可以了吧,上限是最大值,下限是budge / 人数

是的是的

法:排序 O(nlogn) 或者用Stack O(n),不知是否有更好的解法

补充内容 (2018-11-10 11:43):
看到Binary Search看来我还是太年轻了(。

补充内容 (2018-11-10 11:44):
啊 员工的工资是已经排序的话那确实Binary Search……但是不排序的话可能还是O(n)

求问楼主 binary search我也不太明白啊 有可能不求和就能算出k么 只找到临界值的话 比budget高了多少可以算出来么 真心求教

麻烦问一下stack怎么做?实在想不出来。binary search其实跟排不排序没关系。每一次binary search的cost其实还是n,最后的cost会是O(nlog(max - min))

public int findK(int[] salary, int budget) {
        int lo = budget / salary.length;
        int hi = Integer.MIN_VALUE;
        for(int sa : salary) {
            hi = Math.max(hi, sa);
        }
        while(lo < hi) {
            int mid = (hi - lo) / 2 + lo;
            int cost = 0;
            for(int sa : salary) {
                if(sa <= mid) {
                    cost += sa;
                } else {
                    cost += mid;
                }
            }
            if(cost == budget) {
                return mid;
            } else if(cost < budget) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }

这个是code,stack怎么在n之内解出来呢?完全没思路- -

binary search解法有位层主给出了代码,就是在解可能的取值范围内用binary search取数然后拿去验证,但对于小数情况只能求到近似值。不知道有没有更好的解法惹,不过求和应该是必须的

所以这个是未排序的nlogn解法