leetcode
leetcode 2101 ~ 2150
按身高排序

按身高排序

难度:

标签:

题目描述

代码结果

运行时间: 26 ms, 内存: 16.4 MB


import java.util.Arrays;
import java.util.Comparator;
import java.util.stream.Collectors;

public class SortByHeightStream {
    /**
     * 思路:
     * 1. 使用 IntStream.range 创建一个索引流。
     * 2. 使用 boxed() 将索引流装箱。
     * 3. 使用 sorted() 对索引按 heights 降序排序。
     * 4. 使用 map() 映射索引到 names。
     * 5. 使用 toArray() 将结果转换为数组。
     */
    public static String[] sortPeople(String[] names, int[] heights) {
        return Arrays.stream(heights)
                .boxed()
                .sorted((a, b) -> b - a)
                .map(i -> names[Arrays.binarySearch(heights, i)])
                .toArray(String[]::new);
    }

    public static void main(String[] args) {
        String[] names1 = {"Mary","John","Emma"};
        int[] heights1 = {180,165,170};
        System.out.println(Arrays.toString(sortPeople(names1, heights1)));

        String[] names2 = {"Alice","Bob","Bob"};
        int[] heights2 = {155,185,150};
        System.out.println(Arrays.toString(sortPeople(names2, heights2)));
    }
}

解释

方法:

解题思路首先涉及到将名字和对应的身高组合起来,形成一个包含两个元素的列表,其中每个元素是一个包含名字和身高的小列表。接下来,使用列表的sort方法,通过自定义排序键(lambda函数),按照身高降序对这些列表进行排序。排序完成后,从排序后的列表中提取出名字,并按照身高的降序顺序将它们收集到答案列表中。

时间复杂度:

O(n log n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么在解题思路中选择将名字和身高组合成一个列表,而不是使用其他数据结构如字典或元组?
在此题解中,选择将名字和身高组合成列表主要是为了方便在排序过程中同时处理这两个相关联的数据。使用列表(例如 [name, height])的好处是它可以在需要时容易修改元素,而元组虽然更加轻量且不可变,也能达到相同的效果。使用列表或元组而不使用字典的原因是,字典不适用于此场景,因为字典是用于键值对的映射,处理单一键对应多个值时会更复杂,而且字典的遍历和排序不如列表和元组直观。
🦆
在排序时使用lambda函数通过`-item[1]`来实现降序,这种方法和其他可能的降序实现(如reverse参数)相比有什么优势或劣势?
使用lambda函数通过`-item[1]`实现降序的优势在于直接性和简洁性,可以直接在排序键中指定排序的方向,而不需要在sort方法中添加额外的`reverse=True`参数。这种方法的劣势是,它仅适用于数值类型的比较,对于非数值类型的排序则不适用。使用`reverse=True`参数的优势是它更通用,可以用于任何类型的数据排序,并且使排序逻辑更明显,易于理解。
🦆
如果身高数组中包含了相同的身高值,排序结果会如何处理名字的顺序?是否会保持它们在原始数组中的顺序?
Python的sort方法默认是稳定的,这意味着如果身高数组中包含相同的身高值,那么相同身高的个体将会保持它们在原始数组中的相对顺序。因此,在本题解中若有相同的身高值,名字的顺序将会保持不变,按照它们在输入列表中的原始顺序排列。
🦆
在进行列表P的名字提取时,有没有更高效的方法来构建最终的答案列表,可能通过一步到位在排序时直接处理?
一种更高效的方法是在排序时直接使用列表推导或生成器表达式。可以在进行排序后的步骤中直接构建答案列表,例如使用`[p[0] for p in sorted(P, key=lambda x: -x[1])]`。这样做可以减少代码行数,并且可以在一个表达式中完成排序和提取名字的操作,提高代码的简洁性和执行效率。

相关问题