跳至主要內容

2724. 排序方式


2724. 排序方式

🟢   🔗 力扣open in new window LeetCodeopen in new window

题目

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 array
  • fn is a function that returns a number
  • 1 <= 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));
};