《JS玩算法系列》海王的鱼塘

写在前面

不知为什么，感觉2020年面试过程中算法题突然流行了起来，不论你是前端后端还是架构师，面试前都得先来两道算法题热热身。

如果你很干脆的回答不会，hr小姐姐就会吃惊地问你：什么？身为一个前端程序员竟然不会算法？？？ 语气口吻就好比你的亲戚问你：不会吧不会吧！身为一个程序员不会修电脑？？？ 让你心跳加速脸红娇喘羞愧难当...

为了避免这种尴尬的情况出现，今天趁着*领导不在*阳光正好，我们一起来摸一条某大厂中等算法题的大鱼试试看，想看《海王的鱼塘》可以直接跳到尾部挑战一下，不过大冰块建议先从《聪明的销售》看起~

《聪明的销售》

样例：

输入：
[1,1,1,2,2,3]
2
输出：
2

实不相瞒，我看了三遍题目，终于看明白了出题人的意思，不就是数组中删掉n个元素，要求剩余的元素中，相同的元素越多越好嘛！

看明白了题目意思，就已经成功了一半。

既然已经成功了一半，那么趁热打铁，理一下思路吧！

如果想要删掉n个元素，剩余的元素中，相同的元素越多越好，那么：删掉的元素出现的次数肯定是越少越好。

所以这道题其实是求出每个元素出现的次数，只要求出每个元素出现的次数，答案就近在咫尺唾手可得呼之欲出了（大冰块的语文是不是比出题人要好？）。

就这？？？我微微一下，劈里啪啦敲出如下demo：

let arr = ['苹果','苹果','苹果','香蕉','香蕉','橘子','橘子','橘子','草莓','火龙果','火龙果']
let obj = {}
arr.forEach( item => obj.hasOwnProperty(item) ? obj[item]+=1 : obj[item] = 1 )
console.log(obj)  // 控制台输出：{苹果: 3, 香蕉: 2, 橘子: 3, 草莓: 1, 火龙果: 2}

如果要删掉5个，就从数量最少的水果删，删够5个即可，我一眼就看出来草莓1+火龙果2+香蕉2刚好等于5，删掉它们即可。

可是程序并不知道，所以我们应该先根据水果数量对obj进行排序，才能顺利的从少到多依次删除对应水果。

可是object对象真的能排序吗？我知道js里的object对象存在自动排序机制，但是我没有对object对象做过排序，所以本文暂时不做讨论object对象属性排序的问题。保险起见，我们采用人人都会的数组排序方式来解决。

把代码重构如下：

let arr = ['苹果','苹果','苹果','香蕉','香蕉','橘子','橘子','橘子','草莓','火龙果','火龙果']
let resultArr = []
arr.forEach( item => {
    let obj = {name: item, num: 1}
    let i = resultArr.findIndex(element => element.name == item)
    i !== -1 ? resultArr[i].num+=1 : resultArr.push(obj)
})
resultArr.sort((a,b)=>a.num-b.num);
console.log(resultArr) 
// 控制台输出：[{name: "草莓", num: 1},{name: "香蕉", num: 2},{name: "火龙果", num: 2},{name: "苹果", num: 3},{name: "橘子", num: 3}]
Object.keys(obj).length

排序完成，那么从num最小的元素开始删除吧！

如果需要删除5个，则声明一个变量sum赋值为0，从第一个元素开始，把元素的num累加给sum，这样对比 sum是否大于5即可，如果大于5则不能删除，直接结束。如果小于5，则累加下一个元素的num，直到大于5。

代码重构如下

let arr = ['苹果','苹果','苹果','香蕉','香蕉','橘子','橘子','橘子','草莓','火龙果','火龙果']
let resultArr = []
arr.forEach( item => {
    let obj = {name: item, num: 1}
    let i = resultArr.findIndex(element => element.name == item)
    i !== -1 ? resultArr[i].num+=1 : resultArr.push(obj)
})
resultArr.sort((a,b)=>a.num-b.num);
let sum = 0
resultArr.map((item,index)=>{
    sum += item.num
    sum > 5 ? '' : delete resultArr[index]
})
console.log(resultArr) 
// 控制台输出：[empty × 3,{name: "苹果", num: 3},{name: "橘子", num: 3}]

虽然map()方法看起来代码精简了不少，但是从如上代码运行角度来说，map()不能终止，在多个元素的情况下效率并没有for循环高，所以我们把代码优化如下：

let arr = ['苹果','苹果','苹果','香蕉','香蕉','橘子','橘子','橘子','草莓','火龙果','火龙果']
let resultArr = []
arr.forEach( item => {
    let obj = {name: item, num: 1}
    let i = resultArr.findIndex(element => element.name == item)
    i !== -1 ? resultArr[i].num+=1 : resultArr.push(obj)
})
resultArr.sort((a,b)=>a.num-b.num);
let sum = 0
for (let index = 0; index < resultArr.length; index++) {
    sum += resultArr[index].num
    // 三元运算符中不能使用return和break，因为三元运算符中要写表达式。所以暂时写if判断吧~
    if(sum > 5){ 
        break
    }else{
        resultArr.splice(index,1)
        index-- // splice()删除元素后，会改变原数组length，所以要index--
    }
}
console.log(resultArr) 
// 控制台输出：[{name: "苹果", num: 3},{name: "橘子", num: 3}]
		

看起来好像满足了题目的要求，这也没什么难度嘛~下面来封装一下试试看吧：

const smartSale = (array=[],number=0)=>{
    let resultArr = []
    array.forEach( item => {
        let obj = {name: item, num: 1}
        let i = resultArr.findIndex(element => element.name == item)
        i !== -1 ? resultArr[i].num+=1 : resultArr.push(obj)
    })
    resultArr.sort((a,b)=>a.num-b.num);
    let sum = 0
    for (let index = 0; index < resultArr.length; index++) {
        sum += resultArr[index].num
        if(sum > number){ 
            break  // 三元运算符中不能使用return和break，因为三元运算符中要写表达式。所以暂时写if判断吧~
        }else{
            resultArr.splice(index,1)
            index--  // splice()删除元素后，会改变原数组length，所以要index--
        }
    }
    return resultArr.length
}
let arr = ['苹果','苹果','苹果','香蕉','香蕉','橘子','橘子','橘子','草莓','火龙果','火龙果']
smartSale(arr,3)
// 控制台输出：3

测试完美运行！那么考虑一下题目下面的限定条件吧：

即传入的数组length ： 1 ≤ array.length ≤ 1000000，传入的number : 1 ≤ number ≤ 100000

const smartSale = (array=[],number=0)=>{
    if (array.length < 1 || array.length > 1000000) throw new Error("数组的长度范围限制为1-1000000")
    if (number < 1 || number > 100000) throw new Error("要删除的数量范围限制为1-100000")
    let resultArr = []
    array.forEach( item => {
        let obj = {name: item, num: 1}
        let i = resultArr.findIndex(element => element.name == item)
        i !== -1 ? resultArr[i].num+=1 : resultArr.push(obj)
    })
    resultArr.sort((a,b)=>a.num-b.num);
    let sum = 0
    for (let index = 0; index < resultArr.length; index++) {
        sum += resultArr[index].num
        if(sum > number){ 
            break  // 三元运算符中不能使用return和break，因为三元运算符中要写表达式。所以暂时写if判断吧~
        }else{
            resultArr.splice(index,1)
            index--  // splice()删除元素后，会改变原数组length，所以要index--
        }
    }
    return resultArr.length
}

根据这道算法题的思路，我也编了一道算法题供诸君思考：

《海王的鱼塘》

掏出你的大脑袋，开动你的脑筋吧~ 把你的答案码在评论区，供各位海王参考一下~

写在后面