跳至主要內容

2631. 分组


2631. 分组open in new window

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

题目

Write code that enhances all arrays such that you can call the array.groupBy(fn) method on any array and it will return a grouped version of the array.

A grouped array is an object where each key is the output of fn(arr[i]) and each value is an array containing all items in the original array which generate that key.

The provided callback fn will accept an item in the array and return a string key.

The order of each value list should be the order the items appear in the array. Any order of keys is acceptable.

Please solve it without lodash's _.groupBy function.

Example 1:

Input:

array = [

{"id":"1"},

{"id":"1"},

],

fn = function (item) {

return item.id;

}

Output:

{

"1": [{"id": "1"}, {"id": "1"}],

"2": [{"id": "2"}]

}

Explanation:

Output is from array.groupBy(fn).

The selector function gets the "id" out of each item in the array.

There are two objects with an "id" of 1. Both of those objects are put in the first array.

There is one object with an "id" of 2. That object is put in the second array.

Example 2:

Input:

array = [

[1, 2, 3],

[1, 3, 5],

[1, 5, 9]

]

fn = function (list) {

return String(list[0]);

}

Output:

{

"1": [[1, 2, 3], [1, 3, 5], [1, 5, 9]]

}

Explanation:

The array can be of any type. In this case, the selector function defines the key as being the first element in the array.

All the arrays have 1 as their first element so they are grouped together.

{

"1": [[1, 2, 3], [1, 3, 5], [1, 5, 9]]

}

Example 3:

Input:

array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

fn = function (n) {

return String(n > 5);

}

Output:

{

"true": [6, 7, 8, 9, 10],

"false": [1, 2, 3, 4, 5]

}

Explanation:

The selector function splits the array by whether each number is greater than 5.

Constraints:

  • 0 <= array.length <= 10^5
  • fn returns a string

题目大意

请你编写一段可应用于所有数组的代码,使任何数组调用 array. groupBy(fn) 方法时,它返回对该数组 分组后 的结果。

数组 分组 是一个对象,其中的每个键都是 fn(arr[i]) 的输出的一个数组,该数组中含有原数组中具有该键的所有项。

提供的回调函数 fn 将接受数组中的项并返回一个字符串类型的键。

每个值列表的顺序应该与元素在数组中出现的顺序相同。任何顺序的键都是可以接受的。

请在不使用 lodash 的 _.groupBy 函数的前提下解决这个问题。

提示:

  • 0 <= array.length <= 10^5
  • fn 返回一个字符串

解题思路

  1. 创建结果对象:使用一个空对象来存储分组结果。
  2. 遍历数组:使用 forEach 方法遍历调用 groupBy 的数组。
  3. 使用分组函数:对于每个元素,调用 fn(item) 函数以获取分组键。
  4. 构建分组结果
    • 检查结果对象中是否已有该分组键。如果没有,创建一个新的数组。
    • 将当前元素添加到相应的分组中。
  5. 返回结果对象:最后返回分组后的结果对象。

复杂度分析

  • 时间复杂度O(n),其中 n 是数组的长度,因为需要遍历整个数组。
  • 空间复杂度O(n),在最坏情况下,所有元素可能会被分到一个组中。

代码

/**
 * @param {Function} fn
 * @return {Object}
 */
Array.prototype.groupBy = function (fn) {
	let res = {};
	this.forEach((item) => {
		const key = fn(item);
		if (!res[key]) {
			res[key] = [];
		}
		res[key].push(item);
	});
	return res;
};

/**
 * [1,2,3].groupBy(String) // {"1":[1],"2":[2],"3":[3]}
 */

相关题目

题号标题题解标签难度
2624蜗牛排序open in new window[✓]
2626数组归约运算open in new window[✓]
2634过滤数组中的元素open in new window[✓]
2635转换数组中的每个元素open in new window[✓]
2774数组的上界 🔒open in new window