给相同的用户打标签

每个用户有三列id，只要有一种id相同即视为一个用户，要求对一个dataframe打标签。如：
input:
a,b,c
1,33,555
1,44,666
2,44,777
3,55,777
3,66,888
4,77,999
5,88,1000
6,77,333
8,99,555。
output:
a,b,c,label
1,33,555,1
1,44,666,1
2,44,777,1
3,55,777,1
3,66,888,1
4,77,999,2
5,88,1000,3
6,77,333,2
8,99,555,1

这是什么公司的题 请问

用hashmap做吧 感觉不难

大大大大晴 发表于 2019-7-17 02:47
用hashmap做吧 感觉不难

感觉不好做，时间复杂度比较高

更新一下，这道题感觉用传统的方法sort，hashmap的不太好实现，借助图论，对于数据量很大的情况下，用pandas很快可以处理，感觉这也是一个现实工作中常见的case

这应该是一个问题的开头，focus应该是scaling和distributed环境下的扩展吧？

先考虑内存可以保存的情况下，有几个ID，我会准备maintain几个HashMap<String, HashMap<String, Integer>>，时间复杂度应该挺好控制的，但是牺牲了空间。
再考虑内存保存不了的情况，就要具体问题具体分析了，提出不同的解决思路，列下各自的取舍，然后和面试官讨论看他准备聊哪个。

感觉这是一道扩容题，要不断DFS把能遍历到的unvisited && 相关 元素都扫到同一个set里，如果都还有 unvisited 的元素，新建set，继续搞

jev9 发表于 2019-7-19 10:48
更新一下，这道题感觉用传统的方法sort，hashmap的不太好实现，借助图论，对于数据量很大的情况下，用panda ...

我也觉得用Graph的dfs比较好解

boolean[] visited = new boolean[people.length];
int[] color = new int[people.length];
int color = 1;

for(int p = 0; p < people.length; p++) {
   if(!visited[p]) {
        Set<Integer> hset = new HashSet<>();
        colors[p] = color;
           for(int i = 0; i < people[p].length; i++) {
                dfs(visited, people[p][i], people, hset, int[] colors, int color);
        }
        color++;
   }
}


public void dfs(boolean[] visited, int start, int[][] people,  Set<Integer> hset, int[] colors, int color) {
        if(hset.contains(start)) return;
        hset.add(start);
        for(int i = 0; i < people.length; i++) {
                if(!visited[i] && (hset.contains(people[i][0] || hset.contains(people[i][1]) || hset.contains(people[i][1]))) {
                        if(!hset.contains(people[i][0]) dfs(visited, people[i][0], people, hset, colors, color);
                        if(!hset.contains(people[i][1]) dfs(visited, people[i][1], people, hset, colors, color);
                        if(!hset.contains(people[i][2]) dfs(visited, people[i][2], people, hset, colors, color);
                        visited[i] = true;
                        colors[i] = color;
                }
        }
}

最后把相同index的people和colors值 对应一下，这是我的解法，没有Test，不知道好不好使，也希望大牛能指导一下。