https://vancexu.github.io/2015/07/21/intro-to-union-find-data-structure-exercise.html
https://www.cnblogs.com/evasean/p/7204566.html
https://www.cnblogs.com/evasean/p/7204566.html
Given a set of n integers S = {0,1,…,N-1}and a sequence of requests of the following form:
- Remove x from S
- Find the successor of x: the smallest y in S such thaty>=x
design a data type so that all operations(except construction) take logarithmic time or better in the worst case.
分析
题目的要求有一个0~n-1的顺序排列序列S，从S中移除任意x，然后调用getSuccessor(x)，方法将返回一个y，这个y是剩余还在S中满足y>=x的最小的数。举例说明S={0,1,2,3,4,5,6,7,8,9}时
remove 6，那么getSuccessor(6)=7
remove 5，那么getSuccessor(5)=7
remove 3，那么getSuccessor(3)=4
remove 4，那么getSuccessor(4)=7
remove 7，那么getSuccessor(7)=8, getSuccessor(3)=8
而对于没有remove的数x，getSuccessor(x)应该等于几呢？题目没有说，那么就认为等于自身好了，接着上面，getSuccessor(2)=2
根据上面的例子，可以看出，实际上是把所有remove的数做了union，root为子集中的最大值，那么getSuccessor(x)实际就是获取remove数中的最大值+1，根据这个思路，代码如下
3 public class Successor { 4 private int num; 5 private int[] id; 6 private boolean[] isRemove; 7 8 public Successor(int n){ 9 num = n; 10 id = new int[n]; 11 isRemove = new boolean[n]; 12 for (int i = 0; i < n; i++) { 13 id[i] = i; 14 isRemove[i] = false; 15 } 16 } 17 18 public int find(int p) { 19 while (p != id[p]) 20 p = id[p]; 21 return p; 22 } 23 24 public void union(int p, int q) { 25 //此处的union取较大根 26 int pRoot = find(p); 27 int qRoot = find(q); 28 if (pRoot == qRoot) 29 return; 30 else if (pRoot < qRoot) 31 id[pRoot] = qRoot; 32 else 33 id[qRoot] = pRoot; 34 } 35 36 public void remove(int x) { 37 isRemove[x] = true; 38 //判断相邻节点是否也被remove掉了，如果remove掉就union 39 if (x>0 && isRemove[x-1]){ 40 union(x,x-1); 41 } 42 if (x<num-1 && isRemove[x+1]){ 43 union(x,x+1); 44 } 45 } 46 47 public int getSuccessor(int x) { 48 if(x<0 || x>num-1){//越界异常 49 throw new IllegalArgumentException("访问越界!"); 50 }else if(isRemove[x]){ 51 if(find(x)+1 > num-1) //x以及大于x的数都被remove掉了，返回-1 52 return -1; 53 else //所有remove数集中最大值+1，就是successor 54 return find(x)+1; 55 }else {//x未被remove，就返回x自身 56 return x; 57 } 58 }https://jznest.wordpress.com/2014/02/17/algorithm-part-i-successor-with-delete/
Q: Successor with delete. Given a set of N integers S={0,1,…,N−1} and a sequence of requests of the following form:
- Remove x from S
- Find the successor of x: the smallest y in S such that y≥x.
design a data type so that all operations (except construction) should take logarithmic time or better.
This problem uses a similar approach as the previous post in solving the maximum object in the component. To fit in the union-find frame, the remove operation acts like union, well, with what? The answer is, if we remove x at index i in an array, it is the same as union (array[i], array[i+1]) (except for the last element). And the successor of x would be the largest object in the component which x is a member of. Just try this yourself.
public class SuccessorDelete{
private int[] id;
private int[] sz;
private int[] maximum;
public SuccessorDelete(int N){
id = new int[N];
sz = new int[N];
maximum = new int[N];
for (int i = 0; i < N; i++){
id[i] = i;
sz[i] = 1;
maximum[i] = i;
}
}
public int delete(int p){
if (p == id.length - 1) return p; // here if we try to delete the maximum of the whole set, just return it.
return union(p, p + 1);
}
private int union(int p, int q){
int rootP = root(p);
int rootQ = root(q);
if (sz[rootP] >= sz[rootQ]){
sz[rootP] += sz[rootQ];
id[rootQ] = rootP;
if (maximum[rootQ] > maximum[rootP]){
maximum[rootP] = maximum[rootQ];
}
return maximum[rootP];
}else{
sz[rootQ] += sz[rootP];
id[rootP] = rootQ;
if (maximum[rootP] > maximum[rootQ]){
maximum[rootQ] = maximum[rootP];
}
return maximum[rootQ];
}
}
private int root(int p){
while(p != id[p]){
id[p] = id[id[p]]; // path compression
p = id[p];
}
return p;
}
}
