Home | Projects | Notes > Problem Solving > LC - M - 658. Find K Closest Elements (multimap, vector, sort)

LC - M - 658. Find K Closest Elements (multimap, vector, sort)

Solutions in C++

Solution 1

Complexity Analysis:

• $T=O(n\log n)$$T = O(n\log n)$, where $n$$n$ is the number of elements in arr

• $S=O(n)$$S = O(n)$, additional memory space used for multimap

Solution:

xxxxxxxxxx
27
1
// #include <map>
2

3
class Solution {
4
public:
5
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
6

7
        multimap<int, int> m;
8
        vector<int> ret;
9

10
        // Loop through the 'arr', insert each pair {|arr[i] - x|, arr[i]} into multimap
11
        // T = O(nlogn), where n is the size of 'arr'
12
        for (int i = 0; i < arr.size(); i++)
13
        {
14
            int diff = abs(arr[i] - x);
15
            m.insert({diff, arr[i]});   // T = O(logn)
16
        }
17

18
        // T = O(k), where k <= n
19
        for (auto it = m.begin(); k-- > 0; it++)
20
            ret.push_back(it->second);
21

22
        // T = O(nlogn)
23
        sort(ret.begin(), ret.end());
24

25
        return ret;
26
    }
27
};