2724. 排序方式
2724. 排序方式
题目
Given an array arr
and a function fn
, return a sorted array sortedArr
. You can assume fn
only returns numbers and those numbers determine the sort order of sortedArr
. sortedArr
must be sorted in ascending order by fn
output.
You may assume that fn
will never duplicate numbers for a given array.
Example 1:
Input: arr = [5, 4, 1, 2, 3], fn = (x) => x
Output: [1, 2, 3, 4, 5]
Explanation: fn simply returns the number passed to it so the array is sorted in ascending order.
Example 2:
Input: arr = [{"x": 1}, {"x": 0}, {"x": -1}], fn = (d) => d.x
Output: [{"x": -1}, {"x": 0}, {"x": 1}]
Explanation: fn returns the value for the "x" key. So the array is sorted based on that value.
Example 3:
Input: arr = [[3, 4], [5, 2], [10, 1]], fn = (x) => x[1]
Output: [[10, 1], [5, 2], [3, 4]]
Explanation: arr is sorted in ascending order by number at index=1.
Constraints:
arr
is a valid JSON arrayfn
is a function that returns a number1 <= arr.length <= 5 * 10^5
题目大意
给定一个数组 arr
和一个函数 fn
,返回一个排序后的数组 sortedArr
。你可以假设 fn
只返回数字,并且这些数字决定了 sortedArr
的排序顺序。sortedArr
必须按照 fn
的输出值 升序 排序。
你可以假设对于给定的数组,fn
不会返回重复的数字。
提示:
arr
是一个有效的 JSON 数组fn
是一个函数,返回一个数字1 <= arr.length <= 5 * 10^5
解题思路
- 使用
[...arr]
创建当前数组的副本,以避免直接修改原数组。 - 在
sort
方法中,根据传入的键(fn(arr[i])
)定义比较函数,对数组进行排序。 - 最后返回排序后的新数组。
复杂度分析
- 时间复杂度:
O(n log n)
,其中n
是数组的长度,排序算法通常需要O(n log n)
的时间复杂度。 - 空间复杂度:
O(n)
,因为需要创建数组的副本。
代码
/**
* @param {Array} arr
* @param {Function} fn
* @return {Array}
*/
var sortBy = function (arr, fn) {
return [...arr].sort((a, b) => fn(a) - fn(b));
};