LeetCode-2418. Sort the People

LeetCode-2418. Sort the People

難度: easy

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: ["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.

解題流程

1. 先看懂題目想描述甚麼情境
2. 開始想像程式運作該經過哪些流程
3. 將經過的流程所需的判斷跟細節列出
4. 實作列出的流程

先看懂題目想描述甚麼情境

開始想像程式運作該經過哪些流程

將經過的流程所需的判斷跟細節列出

實作列出的流程

typescript

氣泡排序版

function sortPeople(names: string[], heights: number[]): string[] {
    if(!names?.length || !heights?.length) return [];
    bubbleSort(heights, names);
    function swap (array, indexA, indexB) {
        let temp = array[indexA];
        array[indexA] = array[indexB];
        array[indexB] = temp;
    }
    function bubbleSort (arrayStandard, arrayFollow) {
        // i => 5 > 4 > 3 > 2 > 1
        for(let i = arrayStandard.length - 1; i > 0; i--) {
            /**
               j => 0 > 1 > 2 > 3 > 4
               j => 0 > 1 > 2 > 3 
                j => 0 > 1 > 2
                j => 0 > 1
                j => 0 
             */
            for(let j = 0; j < i; j++) {
                if(arrayStandard[j] < arrayStandard[j+1]) {
                    swap(arrayStandard, j, j + 1);
                    swap(arrayFollow, j, j + 1);
                }
            }
        }
    }
    return names;
};

選擇排序版

function sortPeople(names: string[], heights: number[]): string[] {
    if(!names?.length || !heights?.length) return [];
    selectSort(heights, names);
    function swap (array, indexA, indexB) {
        let temp = array[indexA];
        array[indexA] = array[indexB];
        array[indexB] = temp;
    }
    function selectSort (arrayStandard, arrayFollow) {
        for(let i = 0; i < arrayStandard.length - 1; i++) {
            // i => 0 > 1 > 2 > 3 > ..... > arrayStandard.length - 2;
            let maxIndex = i;
            for(let j = i + 1; j < arrayStandard.length; j++) {
                /**

                    the loop start index will be increased by each round(for loop)
                    cuz we've set the smallest number to start index in last round

                    j => i+1(1) > 2 > 3 > .... > arrayStandard.length - 1;
                    maxIndex => smallest j

                    j => i+1(2) > 3 > .... > arrayStandard.length - 1;
                    maxIndex => smallest j

                 */
                if(arrayStandard[maxIndex] < arrayStandard[j]) {
                    maxIndex = j;
                }
            }
            // only if change index needs to swap index position
            if(maxIndex !== i) {
                swap(arrayStandard, i , maxIndex);
                swap(arrayFollow, i , maxIndex);
            }
        }
    }
    return names;
};

感謝閱讀，如果有錯誤或是講得不清楚的部分，再請留言指教