[알고리즘] 리트코드 658. k개의 가장 가까운 요소 찾기 c++ // 이진탐색, 투포인터

* 완탐

-내코드

{차이, idx}를 저장하고

차이로정렬하고, idx로 원본에 다시접근하는방법

매우 비효율적임.

class Solution {
public:
    static bool cmp(pair<int,int> p1, pair<int,int> p2){
        if(p1.first==p2.first){ //인덱스작은거우선
            return p1.second<p2.second;
        }
        return p1.first < p2.first;
    }
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        vector<pair<int,int>> gabs; //{차이, 인덱스}
        for(int i=0;i<arr.size();++i){
            gabs.push_back({abs(x-arr[i]),i});
            //cout<<abs(x-i)<<" "<<i<<"\n";
        }
        sort(gabs.begin(),gabs.end(),cmp);

        // for(auto p : gabs){
        //     cout<<p.first<<" "<<p.second<<"\n";
        // }
        vector<int> ret;
        for(int i=0;i<k;++i){
            ret.push_back(arr[gabs[i].second]);
        }
        sort(ret.begin(),ret.end());
        return ret;
        //O(n lg n) 정렬
    }
};

- 정답코드

굳이 idx를 저장할필요없이 차이로 원본배열을 정렬해버리면됨.

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        stable_sort(begin(arr), end(arr), [x](const auto a, const auto b){
            return abs(a - x) < abs(b - x);   // sort by distance from x
        });
        arr.resize(k);                        // choose first k elements
        sort(begin(arr), end(arr));           // sort the output in ascending order before returning
        return arr; 
    }
};

시간 복잡도: O(nlogn + klogk) //n개정렬 + k 개 정렬

 

* 투포

가능성이없는것을 제거한다!

k개를 고를때까지

우측의 차이가더큰경우 -> 우측을버림

아닌경우 -> 좌측을 버림

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int L = 0, R = size(arr)-1;
        while (R - L >= k) 
            if (x - arr[L] <= arr[R] - x) R--;
            else L++;
        return vector<int>(begin(arr) + L, begin(arr) + R + 1);
    }
};

O(n-k)

 

* 이진 + 투포

정렬된배열은? 이진탐색

[1 2 3 4 5]

    L R

R==lb로 두고, 차이가 작은것을 하나씩 선택해나간다!

if(R >= n || L >= 0 && x - arr[L] <= arr[R] - x) L--;

 

R이없거나, L이 정상범위인경우 L을 선택해야함.

 

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {        
        int n = size(arr), R = lower_bound(begin(arr), end(arr), x) - begin(arr), L = R - 1;
		// expand the [L, R] window till its size becomes equal to k
        while(k--) 
            if(R >= n || L >= 0 && x - arr[L] <= arr[R] - x) L--;  // expand from left
            else R++;                                              // expand from right
        return vector<int>(begin(arr) + L + 1, begin(arr) + R);
    }
};

O(lg n )이진탐색1회 + O(k) k 번 탐색

 

 

* 솔루션 링크

https://leetcode.com/problems/find-k-closest-elements/solutions/1310981/simple-solutions-w-explanation-all-possible-approaches-explained/