First pass, construct an array that contain key and count pairs, for example, (1,4) means 1 is printed 4 times and the first case would be (1,4) (M, 4) (3,3) … etc.
Then construct a 2D array that traverse the above array that would contain the chars as how they should be printed as. To save space, I think you could also traverse the above array backward, and process the highest count ones, while subtracting one. Then continue until there is nothing left in that array.
class UnionFind():
def __init__(self, N):
self.items = [[i] for i in range(N)]
def _find_index(self, item):
for i in range(len(self.items)):
if item in self.items[i]:
return i
return None
def union(self, a, b):
aIndex = self._find_index(a)
bIndex = self._find_index(b)
if aIndex is not None and bIndex is not None and aIndex != bIndex:
self.items[bIndex] += self.items[aIndex]
del self.items[aIndex]
def getGroupCount(self):
return len(self.items)
n = 4
matrix = ['1100', '1110', '0110','0001']
UF = UnionFind(n)
for i in range(n):
for j in range(i+1, n):
if matrix[i][j] == '1' and i != j:
UF.union(i, j)
print(UF.getGroupCount())
public static int countGroups(List<String> related) {
int n = related.size();
UF uf = new UF(n);
for (int r = 0; r < n; r++) {
String row = related.get(r);
for (int c = 0; c < n; c++) {
if (row.charAt(c) == '1') {
uf.union(r, c);
}
}
}
return uf.size();
}
class UF {
private int[] parent;
private byte[] rank;
private int size;
public UF(int n) {
if (n < 0) throw new IllegalArgumentException();
parent = new int[n];
rank = new byte[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
size = n;
}
public int find(int p) {
while (p != parent[p]) {
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
public void union(int p, int q) {
int pr = find(p);
int qr = find(q);
if (pr == qr) return;
if (rank[pr] < rank[qr]) {
parent[pr] = qr;
} else {
parent[qr] = pr;
if (rank[pr] == rank[qr]) rank[pr]++;
}
size--;
}
public int size() {
return size;
}
}
static Map<Integer, Node> graph = new HashMap<>();
static class Node {
int rank;
Node parent;
Node() {
rank = 0;
parent = this;
}
}
private static Node findParent(Node node) {
if (node == node.parent) return node;
node.parent = findParent(node.parent);
return node.parent;
}
private static void union(Node node1, Node node2) {
Node p1 = findParent(node1);
Node p2 = findParent(node2);
if (p1 == p2) return;
if (p1.rank >= p2.rank) {
p2.parent = p1;
p1.rank += 1;
} else {
p1.parent = p2;
p2.rank += 1;
}
}
public static int countGroups(List<String> related) {
for(int i = 0; i < related.size(); i++) {
graph.put(i, new Node());
}
for(int i = 0; i < related.size(); i++) {
for(int j = i+1; j < related.size(); j++) {
if (related.get(i).charAt(j) == '1') {
union(graph.get(i), graph.get(j));
}
}
}
Set<Node> set = new HashSet<>();
for(int i = 0; i < related.size(); i++) {
set.add(findParent(graph.get(i)));
}
return set.size();
}
