본문 바로가기

Programming Problems/Hashing

URL 배열 중에서 중복되지 않은 첫 원소 찾기

제곧내


해시 테이블에 "반복되지 않은" 원소들을 넣는다. 즉, 처음 만난 원소면 넣고, 리스트에 append하고 그 포인터를 맵에 저장한다.

만약 반복되면 그 리스트 포인터를 지우고 포인터를 널로 만든다. 이미 널이면 이미 두번 이상 나왔다는 거니까 무시한다.


string findfirstuniqueURL(vector<string> & data){

// make buffer elements

list<string> tmp;

unordered_map<string,list<string>::iterator> buffer;

// go through data

for(int i = 0 ; i  < data.size() ; i++){

auto it = buffer.find(data[i]);

if(it!=buffer.end()){

if(it->second!=NULL){

tmp.erase(it->second);

it->second==NULL;

}

}else{

list.push_back(data[i]);

buffer.insert(pair<string,list<string>::iterator>(data[i],--list.end()));

}

}

// return first element in list

return list.front();

}


time complexity : O(N)

space complexity : O(N)


OK..!!