LeetCode 952. Calculate Maximum Component Size by Common Factor

952. By common factorCalculate maximum component size

[Prime factor + Union search] At first, I thought about using gcd to check the common factor. If it is not 1, then use union search and merge, but the complexity is O(n * n * gcd), O(gcd) = O(logm), so obviously it times out.

Another way of thinking, you can find all the divisors of each number, and then use the divisors as the key and the list of numbers as the value to store in the hash table, and merge the numbers under the list with the same key into the same key each time.The complexity of the search set is only O(n * logm), and it is found that nums are different, so it can be discretized to map [1, 10^5] to [1, 2 * 10^4], that is, the storage in the list.The subscript of the array, and the subscript of the merged element in the union search.

The prime factor can be written like this:

for(i = 2; i * i <= n; i++) {

if (n * i== 0) i-> yes;

while (n % i == 0) n /= i; // divide the factor cleanly

}

if(n != 1) n-> yes; // don't forget to add n to the final result at the end

class Solution {public:int N = (int)2e4 + 1;int *f;int *d;int ans = 1;int ask(int x) {return x == f[x]? x: ask(f[x]);}void merge(int x, int y) {x = ask(x);y = ask(y);if (x == y) return;d[x] += d[y];f[y] = f[x];ans = max(d[x], ans);}int largestComponentSize(vector& nums) {int n = nums.size();f = (int*)malloc(sizeof(int) * N);d = (int*)malloc(sizeof(int) * N);unordered_map> m;for (auto i = 0; i < N; i++) f[i] = i;for (auto i = 0; i < N; i++) d[i] = 1;for (auto i = 0; i < n; i++) {int x = nums[i];for (auto j = 2; j * j <= x; j++) {if (x % j == 0) m[j].push_back(i);while (x % j == 0) x /= j;}if (x != 1) m[x].push_back(i);}for (auto & it: m) {vector l = it.second;int tmp = l.size();for (auto i = 1; i < tmp; i++) {merge(l[i - 1], l[i]);}}return ans;}};

class Solution {// and lookup set 10:31 13int N = 20001;int[] f = new int[N];int[] cnt = new int[N];int ans = 1;int gcd(int a, int b) {return a % b == 0? b: gcd(b, a % b);}int ask(int x) {return x == f[x]? x: ask(f[x]);}void union(int x, int y) {x = ask(x); y = ask(y);if (x == y) return;cnt[x] += cnt[y];f[y] = x;ans = Math.max(ans, cnt[x]);}public int largestComponentSize(int[] nums) {for (var i = 0; i < N; i++) f[i] = i;Arrays.fill(cnt, 1);int n = nums.length;Map> map = new HashMap<>();for (var i = 0; i < n; ++i) {var x = nums[i];for (var j = 2; j * j <= x; j++) {if (x % j == 0) {map.computeIfAbsent(j, k -> new ArrayList()).add(i);}while (x % j == 0) x /= j;}if (x != 1)map.computeIfAbsent(x, k -> new ArrayList()).add(i);}for (var k: map.keySet()) {var list = map.get(k);int m = list.size();for (var i = 1; i < m; i++) {union(list.get(i - 1), list.get(i));}}return ans;}}