.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Plain Text
복사
Example 2:
Input: nums = [1], k = 1
Output: [1]
Plain Text
복사
Constraints:
•
1 <= nums.length <= 105
•
k is in the range [1, the number of unique elements in the array].
•
It is guaranteed that the answer is unique.
Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
My solution
정수 배열 nums와 k개 주어지면, 가장 자주 사용하는 k 개의 요소를 반환한다. 어떤 순서든 가능하다.
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Docker
복사
k가 2이면 2개의 가장 자주 사용되는 요소를 반환한 것이다.
hash table을 사용하거나 map 객체를 사용해서 각 요소별로 개수를 센다.
완성된 해시테이블은 이차원 배열화하면 sort할 수 있게 된다.
sort만 하면 이제 key([0])만 map 메서드로 뽑아낸 배열을 만들 수 있다.
이렇게 만든 배열을 k개만큼만 잘라서 반환하면 된다.
Code
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
const topKFrequent = function (nums, k) {
// use a map
const myMap = new Map();
for (const x of nums) {
if (myMap.has(x)) {
myMap.set(x, myMap.get(x) + 1);
} else {
myMap.set(x, 1);
}
}
return [...myMap.entries()]
.sort((a, b) => b[1] - a[1])
.map(v => v[0])
.slice(0, k);
// use a hash table
// const hash = {};
// for (const x of nums) {
// if (hash[x]) {
// hash[x]++;
// } else {
// hash[x] = 1;
// }
// }
// return [...Object.entries(hash)]
// .sort((a, b) => b[1] - a[1])
// .map(v => parseInt(v[0], 10))
// .slice(0, k);
};
describe('topKFrequent', () => {
it('TC1', () => {
expect(topKFrequent([1, 1, 1, 2, 2, 3], 2)).toStrictEqual([1, 2]);
});
it('TC2', () => {
expect(topKFrequent([1], 1)).toStrictEqual([1]);
});
it('TC3', () => {
expect(topKFrequent([1, 2], 2)).toStrictEqual([1, 2]);
});
it('TC4', () => {
expect(topKFrequent([4, 1, -1, 2, -1, 2, 3], 2)).toStrictEqual([-1, 2]);
});
});
JavaScript
복사
