LeetCode（Sorting)2418. Sort the People

旧城等待， 2023-09-23 23:23 27阅读 0赞

# 1.问题 #

You are given an array of strings names, and an array heights that consists of distinct positive integers. Both arrays are of length n.

For each index i, names\[i\] and heights\[i\] denote the name and height of the ith person.

Return names sorted in descending order by the people’s heights.

Example 1:

> Input: names = \[“Mary”,“John”,“Emma”\], heights = \[180,165,170\]  
> Output: \[“Mary”,“Emma”,“John”\]  
> Explanation: Mary is the tallest, followed by Emma and John.

Example 2:

> Input: names = \[“Alice”,“Bob”,“Bob”\], heights = \[155,185,150\]  
> Output: \[“Bob”,“Alice”,“Bob”\]  
> Explanation: The first Bob is the tallest, followed by Alice and the second Bob.

Constraints:

*  n == names.length == heights.length
 *  1 <= n <= 103
 *  1 <= names\[i\].length <= 20
 *  1 <= heights\[i\] <= 105
 *  names\[i\] consists of lower and upper case English letters.
 *  All the values of heights are distinct.

# 2. 解题思路 #

## 方法1： ##

> 1.定义names或heights的长度为length，新建数组result存储返回后的数组  
> 2.新建TreeMap，将键和值存储，使用TreeMap的原因是根据key能够升序排序，map不能够升序排序  
> 3.循环遍历，将key和value放入map  
> 4.遍历map，从后向前遍历值，并将值存入result  
> 5.返回result

## 方法2： ##

> 1.新建map，遍历数组，将key和value存入map  
> 2.对map的key进行升序排序  
> 3.新建数组长度为heights.length，定义index索引值为0  
> 4.for循环，从后向前遍历map指定位置的值，并将值存入result

## 方法3： ##

> 1.新建treeMap，Collections.reverseOrder()的key降序排序  
> 2.循环遍历，将key和value放入map  
> 3.定义count的初始为0  
> 4.遍历循环，map.keySet()是取出map中所有key,通过get（key)方法取出value的值并存入names  
> 5.返回names

# 3. 代码 #

## 代码1： ##

class Solution {
        
        public String[] sortPeople(String[] names, int[] heights) {
        
            int length=names.length;//1.定义names或heights的长度为length，新建数组result存储返回后的数组
            String[] result = new String[names.length];
            TreeMap<Integer,String> map = new TreeMap<Integer,String>();//2.新建TreeMap，将键和值存储，使用TreeMap的原因是根据key能够升序排序，map不能够升序排序
            for (int i = 0; i < names.length; i++) {
        //3.循环遍历，将key和value放入map
                map.put(heights[i],names[i]);
            }
            for(Map.Entry m:map.entrySet()){
        //4.遍历map，从后向前遍历值，并将值存入result
                result[--length] = (String) m.getValue();
            }        
            return result; //5.返回result
        }
    }

## 代码2： ##

class Solution {
        
        public String[] sortPeople(String[] names, int[] heights) {
        
            Map<Integer, String> map = new HashMap<>();//1.新建map，遍历数组，将key和value存入map
            for (int i = 0; i < names.length; i++) {
        
                map.put(heights[i], names[i]);
            }
            Arrays.sort(heights);//2.对map的key进行升序排序
            String[] result = new String[heights.length];//3.新建数组长度为heights.length，定义index索引值为0
            int index = 0;
            for (int i = heights.length - 1; i >= 0; i--) {
        //4.for循环，从后向前遍历map指定位置的值，并将值存入result
                result[index] = map.get(heights[i]);
                index++;
            }
            return result;
        }
    }

> 和代码2的思路基本相同

class Solution {
        
        public String[] sortPeople(String[] names, int[] heights) {
        
            int length = heights.length;
            Map<Integer, String> map = new HashMap();
            for(int i=0; i<length; i++){
        
                map.put(heights[i], names[i]);
            }
            Arrays.sort(heights);
            String[] res = new String[length];
            for(int i=length-1, j=0; i>=0; i--){
        
                res[j++] = map.get(heights[i]);
            }
            return res;
        }
    }

> 利用桶的思路解题

class Solution {
        
        public String[] sortPeople(String[] names, int[] heights) {
        
            
            String[] res = new String[names.length];
            int[] indexOfNames = new int[100001];
            
            for(int i = 0; i < heights.length; i++){
        
                indexOfNames[heights[i]] = i;
            }
                
            Arrays.sort(heights);
            
            for(int i = 0; i < heights.length; i++){
        
                res[heights.length - i - 1] = names[indexOfNames[heights[i]]];        
            }
            
            return res;    
        }
    }

class Solution {
        
        public String[] sortPeople(String[] names, int[] heights) {
        
            Map<Integer, String> map = new TreeMap<>(Collections.reverseOrder());
            for (int i = 0; i < names.length; i++) {
        
                map.put(heights[i], names[i]);
            }
    
            int count = 0;
            for (Integer key : map.keySet()) {
        
                names[count++] = map.get(key);
            }
            return names;
        }
    }

## 代码3 ##

class Solution {
        
        public String[] sortPeople(String[] names, int[] heights) {
        
            Map<Integer, String> map = new TreeMap<>(Collections.reverseOrder());//1.新建treeMap Collections.reverseOrder()的key降序排序
            for (int i = 0; i < names.length; i++) {
        //2.循环遍历，将key和value放入map
                map.put(heights[i], names[i]);
            }
    
            int count = 0;//3.定义count的初始为0
            for (Integer key : map.keySet()) {
        //4.遍历循环，map.keySet()是取出map中所有key,通过get（key)方法取出value的值并存入names
                names[count++] = map.get(key);
            }
            return names;//5.返回names
        }
    }