friend recommend
구두 달리기 프로그램, 런은 여러 개의 케이스를 사용했다. 처음에 나는 A와 관계가 있는 모든'친구'를 찾아냈다. 나중에 면접관은 A의 친구(2층)만 찾으면 A를 포함할 수 없는 친구를 찾을 수 있다고 제시했다.하나의 그림을 검색하고 그림의 깊이를 기록하는 데gree...
//return friends of friends that are not this person's friends
//Friend Recommendation:bucket sort,O(m) time,O(n) space,m is num of person's friends' friends,n is num of valid friends
public class Solution {
public class Person {
int id;
HashSet friends = new HashSet<>();
}
private List friendsRecommend(Person person, int k) {
List res = new ArrayList<>();
if (person == null) {
return res;
}
HashMap map = new HashMap<>();
for (int friend : person.friends) {
for (int recommend : friend.friends) {
int id = recommend.id;
if (person.friends.contains(id) || id == person.id) {
continue;//if person already has this friend,or this is person himself/herself,continue
}
if (!map.containsKey(id)) {
map.put(id, 0);
}
map.put(id, map.get(id) + 1);
}
}
List> buckets = new ArrayList<>();
for (int i = 0; i <= nums.length; i++) {
buckets.add(new ArrayList());//we use frequency as index, so <= length
}
for (int key : map.keySet()) {//unlike heap solution, we only need keySet() here
buckets.get(map.get(key)).add(key);//get the id(key), add the id to its frequency bucket
}
for (int i = buckets.size() - 1; i >= 0; i--) {
for (int j = 0; j < buckets.get(i).size(); j++) {//start adding the vals at the last bucket's last index
res.add(buckets.get(i).get(j));
if (res.size() == k) {
return res;//this two loops are O(k) time, when res has k nums, return it
}
}
}
return res;
}
}
//Friend Recommendation: Quick Select, average O(m + n) time, O(1) space, worst case O(m + n^2) time
//m is num of person's friends' friends,n is num of valid friends
public class Solution {
public class Person {
int id;
HashSet friends = new HashSet<>();
}
private List friendsRecommend(Person person, int k) {
List res = new ArrayList<>();
if (person == null) {
return res;
}
HashMap map = new HashMap<>();
for (int friend : person.friends) {
for (int recommend : friend.friends) {
int id = recommend.id;
if (person.friends.contains(id) || id == person.id) {
continue;//if person already has this friend,or this is person himself/herself,continue
}
if (!map.containsKey(id)) {
map.put(id, 0);
}
map.put(id, map.get(id) + 1);
}
}
ArrayList> list = new ArrayList<>(map.entrySet());
int left = 0;
int right = list.size() - 1;
int index = -1;
while (true) {
int pos = partition(list, left, right);
if (pos + 1 == k) {
index = pos;
break;
} else if (pos + 1 > k) {
right = pos - 1;
} else {
left = pos + 1;
}
}
if (index == -1) {
return res;
}
for (int i = 0; i <= index; i++) {
int id = list.get(i).getKey();
res.add(id);
}
return res;
}
private int partition(ArrayList> list, int left, int right) {
Random rand = new Random();
int index = rand.nextInt(right - left + 1) + left;//remember to add + left !!!
Map.Entry pivot = list.get(index);
int pVal = pivot.getValue();
swap(list, left, index);//index, not pivot !!
int l = left + 1;
int r = right;
while (l <= r) {
int lVal = list.get(l).getValue();
int rVal = list.get(r).getValue();
if (lVal < pVal && rVal > pVal) {
swap(list, l, r);
}
if (lVal >= pVal) {
l++;
}
if (rVal <= pVal) {
r--;
}
}
swap(list, left, r);
return r;
}
private void swap(ArrayList> list, int left, int right) {
Map.Entry temp = list.get(left);
list.set(left, list.get(right));
list.set(right, temp);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.