1202. Smallest String With Swaps[没有解出]

Union Find讲解

本题是一个很好的学习Union Find的机会，下面的一个Implementation叫做Quick Union，肯定不是最好的，但是是相对好理解的：

Set-Up

把每个元素的parent都设定为为自己

for (int i = 0; i < parent.length; ++i) {
    parent[i] = i;
}

Find

就是寻找root。

• 时间复杂度：最差是

  private int root(int[] parent, int idx) {
    while (idx != parent[idx]) {
        idx = parent[idx];
    }
    return idx;
  }

  Union

  就是找到两个点分别的root，将其中一个点定为另一个点的parent

• 时间复杂度：

  private void union(int[] parent, int idx1, int idx2) {
    int root1 = root(parent, idx1);
    int root2 = root(parent, idx2);
    if (root1 < root2) {
        parent[root2] = root1;
    }
    else {
        parent[root1] = root2;
    }
  }
  

  题解

  本题主流方法是Union Find，大致做法：

1. 运用Union Find把所有点分为几类，不同点有不同的root
   
2. 之后存在一个key是root，value是相同root的所有点，并且按大小顺序排列，所以是Map<Integer, PriorityQueue<Integer>>
   
3. 构建新的String，从前往后遍历，每个index都放对应root所拥有的最小的char，最后就能构架出来
   

• 时间复杂度：
  • 比较难分析，略过
    
• 空间复杂度：
  • 一个parent数组，一个HashMap
    
  • 所以是

本题不算难，但是第一次见很难完美解出解答，这是一个很好的学习过程

class Solution {
  public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
    int[] parent = new int[s.length()];

    for (int i = 0; i < parent.length; ++i) {
      parent[i] = i;
    }

    for (List<Integer> pair : pairs) {
      union(parent, pair.get(0), pair.get(1));
    }

    Map<Integer, PriorityQueue<Character>> map = new HashMap<>();
    for (int i = 0; i < s.length(); ++i) {
      int idx = root(parent, i);
      map.putIfAbsent(idx, new PriorityQueue<>());
      map.get(idx).offer(s.charAt(i));
    }

    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < s.length(); ++i) {
      sb.append(map.get(root(parent, i)).poll());
    }
    return sb.toString();
  }

  private void union(int[] parent, int idx1, int idx2) {
    int root1 = root(parent, idx1);
    int root2 = root(parent, idx2);

    if (root1 < root2) {
      parent[root2] = root1;
    }
    else {
      parent[root1] = root2;
    }
  }

  private int root(int[] parent, int idx) {
    while (idx != parent[idx]) {
      idx = parent[idx];
    }
    return idx;
  }
}