狗家电面

hjldtc 发表于 2021-02-12 12:24:16
不行呀  k = 2
range: ,,]
那不就所有数字都到一个range里面去了？

是的，我错了，我在后面的楼里承认错误了，不好意思，误解您了

补充内容 (2021-2-13 06:37):
误导

第一题的利口题号是什么呀？ 谢谢啦

为了保证顺序就直接union find 复杂度nk 可以用treemap来确定最终顺序也是按照索引顺序走的

c# 实现了下
先通过union find来分组 然后一个个组打印出来就好了

1. class HelloWorld {
   
2.     static void Main() {
   
3.         var test = new int[] { 4, 3, 7, 6, 9, 2 };
   
4.         int k = 1;
   
5.         
   
6.         var uf = new UnionFind(test.Length);
   
7.         
   
8.         for (int i=0; i<test.Length-1; i++) {
   
9.             for (int j=i+1; j<test.Length; j++) {
   
10.                 if (NumsWithinRange(test[i], test[j], k)) {
    
11.                     uf.Union(i, j);
    
12.                 }
    
13.             }
    
14.         }
    
15.         var res = new Dictionary<int, IList<int>>();
    
16.         
    
17.         for (int i=0; i<test.Length; i++) {
    
18.             int groupNumber = uf.Find(i);
    
19.             if (!res.ContainsKey(groupNumber)) {
    
20.                 res[groupNumber] = new List<int>();
    
21.             }
    
22.             res[groupNumber].Add(test[i]);
    
23.         }
    
24.         
    
25.         foreach (var ls in res) {
    
26.             Console.Write("\n");
    
27.             foreach (var item in ls.Value) {
    
28.                 Console.Write(item + ", ");
    
29.             }
    
30.         }
    
31.         
    
32.     }
    
33.    
    
34.     public static bool NumsWithinRange(int x, int y, int range) {
    
35.         int diff = Math.Abs(x - y);
    
36.         return diff <= range;
    
37.     }
    
38. }
    
39. 
    
40. public class UnionFind {
    
41.     public int[] parent, rank;
    
42.     public int groups;
    
43.    
    
44.     public UnionFind(int n) {
    
45.         parent = new int[n];
    
46.         rank = new int[n];
    
47.         for (int i=0; i<n; i++) {
    
48.             parent[i] = i;
    
49.         }
    
50.         groups = n;
    
51.     }
    
52.    
    
53.     public void Union(int x, int y) {
    
54.         int px = Find(x);
    
55.         int py = Find(y);
    
56.         if (px == py) return;
    
57.         
    
58.         if (rank[px] > rank[py]) {
    
59.             parent[py] = px;
    
60.             rank[px]++;
    
61.         } else {
    
62.             parent[px] = py;
    
63.             rank[py]++;
    
64.         }
    
65.         groups--;
    
66.     }
    
67.    
    
68.     public int Find(int x) {
    
69.         while (parent[x] != x) {
    
70.             return Find(parent[x]);
    
71.         }
    
72.         return x;
    
73.     }
    
74. }

复制代码

[/i][/i][/i]

第一题lc见过，死活找不到，有大神share下题号么

结合大家的答案我写个O（N）比较糙

1. import math
   
2. def find_group(numbers, k):
   
3.     min_val = min(numbers)
   
4.     max_val = max(numbers)
   
5.     num_bucket = math.ceil(1.0*(max_val-min_val+1)/(k+1))
   
6.     print(num_bucket)
   
7.     buckets = [[] for _ in range(num_bucket)]
   
8. 
   
9.     for num in numbers:
   
10.         bucket_index = (num-min_val)//(k+1)
    
11.         # can add local_min and local_max for each bucket
    
12.         buckets[bucket_index].append(num)
    
13.     print(buckets)
    
14.     res = []
    
15.     i = 0
    
16.     while i < num_bucket:
    
17.         if len(buckets[i]) == 0:
    
18.             i += 1
    
19.             continue
    
20. 
    
21.         tmp = []
    
22.         if i+1 < num_bucket and len(buckets[i+1]) != 0 and max(buckets[i+1])-min(buckets[i]) <= k:
    
23.             tmp += buckets[i]
    
24.             tmp += buckets[i+1]
    
25.             i += 2
    
26.         else:
    
27.             tmp += buckets[i]
    
28.             i += 1
    
29.         res.append(tmp)
    
30.    
    
31.     return res
    
32.         
    
33. nums = [4, 3, 7, 6, 9, 2, 10, 11, 13, 20]
    
34. k = 2
    
35. print(find_group(nums, k))
    

复制代码

木华黎_Reid 发表于 2021-12-1 15:01
结合大家的答案我写个O（N）比较糙

非常感谢你的答案！！大赞！！