乐趣区

关于leetcode:力扣之按身高排序

题目形容

给你一个字符串数组 names,和一个由 互不雷同 的正整数组成的数组 heights。两个数组的长度均为 n

对于每个下标 inames[i] 和 heights[i] 示意第 i 集体的名字和身高。

请按身高 降序 程序返回对应的名字数组 names

示例 1:

输出:names = ["Mary","John","Emma"], heights = [180,165,170]
输入:["Mary","Emma","John"]
解释:Mary 最高,接着是 Emma 和 John。

示例 2:

输出:names = ["Alice","Bob","Bob"], heights = [155,185,150]
输入:["Bob","Alice","Bob"]
解释:第一个 Bob 最高,而后是 Alice 和第二个 Bob。

力扣原题目地址:https://leetcode.cn/problems/…

思路解法

剖析

  • 题目中有两块信息,别离是对应的身高数组和姓名数组,不过最终要求的后果却是,依照身高数组的排序返回对应的姓名数组。
  • 一想到排序,咱们首先要想到 js 中的 sort(function(a-b){}) 排序办法。不过平时应用这个 api 的时候,咱们经常是用做一维数组的排序。
  • 实际上二维数组也能够应用这个 api 的,为什么会提到二维数组呢?
  • 因为单个的信息蕴含两个变量:姓名和身高。所以应用二维数组最合适

思路步骤

  1. 创立一个二维数组,二维数组中的每一项又是一个小数组,一个个的小数组中都寄存两个值,某人的名字和身高。
  2. 而后依据身高排序
  3. 将排好序的二维数组遍历,取出其中的名字即可

代码

应用 Map 汇合转二维数组

function sortPeople(names, heights) { // 留神 heights 数组没有反复项(names 数组可能有反复项)// 两个对应数组,等同长度,取谁的长度都行
        let n = names.length
        // 首先将名字身高组合成一个 map 汇合
        let map = new Map()
        for (let i = 0; i < n; i++) {map.set(heights[i], names[i]) // 取谁,value 就是谁
        }
        // 而后将 map 汇合转换成二维数组,并调用原生 js 的 api 排序
        let sort2WeiArr = [...map].sort(function (a, b) {return b[0] - a[0] // 记不清 a - b 还是 b - a 没关系,打印看下就行了
        })
        // 排好序的二维数组再遍历,取出名字项即可
        let result = sort2WeiArr.map((item) => {return item[1]
        })
        return result
}
const res = sortPeople(names, heights)
console.log('排序后果', res)

tips: Map 汇合转二维数组:[...Map] 这样写就解构转二维数组了

提交后果图

原地转二维数组

这个就是不应用 Map 汇合了,间接原地转,赋值代替,将原来的一维数组转成二维数组,如下代码:

function sortPeople(names, heights) {
        let n = names.length
        for (let i = 0; i < n; i++) {
                // 原地转二维数组,当然也能够定义一个数组来转,不过消耗内存
                // 如:newArr[i] = [heights[i], names[i]] 
                heights[i] = [heights[i], names[i]] // 原地摇身一变,一维成二维的了
        }
        // 二维数组排好序
        let sort2WeiArr = heights.sort(function (a, b) {return b[0] - a[0]
        })
        // 排好序的二维数组再遍历,取出名字项即可
        let result = sort2WeiArr.map((item) => {return item[1]
        })
        return result
}
const res = sortPeople(names, heights)
console.log('排序后果', res)

提交后果图

比照上述两张后果图,发现第二种形式优于第一种形式

总结

本道题目,温习坚固了以下常识:

  • map 汇合转二维数组的写法
  • 二维数组应用 sort 办法排序
  • 一位数组原地转成二维数组

揭示:有的道友可能会这样写,这样写性能就不好了

// 好的形式
let n = names.length
let map = new Map()
for (let i = 0; i < n; i++) {map.set(heights[i], names[i]) // 取谁,value 就是谁
}

// 不好的形式
let map = new Map()
for (let i = 0; i < names.length; i++) {for (let j = 0; j < heights.length; j++) {if(i == j){map.set(heights[i], names[i]) 
        }
    }
}

// 起因不赘述,大家都懂
退出移动版