모든 row와 column이 sorted 일때, K번쨰 작은 원소 찾기

저번에도 했었는데 자신보다 작으면서 가장 큰 n*(n-1)/2 를 찾는다. 그 다음 row에서 K-x 번째 원소를 찾는다.

time complexity : O(N) (!!!)

space complexity : O(1) (!!!)

구현하기 귀찮은데.. 내일이 면접이니 해볼까? 아니.. 후회할까? 글쎄.. 귀찮은데

코드를 짜면서 헤메면 보기 매우 안좋다. 코드는 정말 알고리즘 및 필요한 자료구조와 계산을 완벽히 정리한 후에

깃발 꽂는 용도로만 쓴다. 아주 구체적으로 알고리즘을 먼저 짜자.

int findKthelement(vector<vector<int>> & data, int K){

// find the matching diagonal index

int n = data.size();

int flag = 0;

// element to find in buffer

int tofind = 0;

K--;

int x,y;

if(K<=(n*(n+1)/2)){

y = (sqrt(1+8*K)-1/2);

x = 0;

tofind = K-y*(y+1)/2;

}else{

x = (sqrt(1+8*(n*n-K))-1/2);

tofind = x+1-(n*n-K-1-x*(x+1)/2);

y = data.size()-1;

}

vector<int> buffer;

while(x<data.size()&&y>=0){

buffer.push_back(data[x][y]);

x++;

y--;

}

return findKthpartition(buffer, tofind);

}