问题:
给你一个字符串数组 names ,和一个由 互不相同 的正整数组成的数组 heights 。两个数组的长度均为 n 。
对于每个下标 i,names[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 。
提示:
n == names.length == heights.length
1 <= n <= 103
1 <= names[i].length <= 20
1 <= heights[i] <= 105
names[i] 由大小写英文字母组成
heights 中的所有值互不相同
思想:
根据快速排序算法思想对heights数组降序排序,并在此过程对names数据进行对应的排序。
代码:
class Solution {public String[] sortPeople(String[] names, int[] heights) {quickSort(heights,names,0,heights.length - 1 );return names;}public void quickSort(int[] height, String[] names, int hl, int hr){if(hl >= hr) return ;int mid = partition(height,names,hl,hr);quickSort(height,names,hl,mid - 1);quickSort(height,names,mid + 1,hr);}public int partition(int[] height, String[] names,int hl, int hr){int piovt = height[hr];int left = hl;int right = hr - 1;while(left <= right){while(left <= right && height[left] >= piovt) left++;while(left <= right && height[right] < piovt) right--;if(left < right){swapHeight(left,right,height);swapString(left,right,names);}}swapHeight(left,hr,height);swapString(left,hr,names);return left;}public void swapHeight(int i, int j, int[] height){int t = height[i];height[i] = height[j];height[j] = t;}public void swapString(int i, int j, String[] names){String t = names[i];names[i] = names[j];names[j] = t;}
}