YuHang’s Blog

并查集系列（三）——继承者问题

发表于 | 分类于

Given a set of N integers S={0,1,…,N−1} and a sequence of requests of the following form:

  1. Remove x from S
  2. Find the successor of x: the smallest y in S such that y≥x.
  3. design a data type so that all operations (except construction) should take logarithmic time or better.

    问题描述

    　　Given a set of N integers S={0,1,…,N−1} and a sequence of requests of the following form:
  4. Remove x from S
  5. Find the successor of x: the smallest y in S such that y≥x.
  6. design a data type so that all operations (except construction) should take logarithmic time or better.

思路分析

　　首先来看题目要求是对数时间，这样的话肯定不可能遍历完整个数组（这样至少为ｎ），加之这一部分学的是并查集。。所以思考怎么使用并查集来解决这个问题。这个问题思考了很久啊。。一直没有答案，这里不得不吐槽一下国内写的博客。。完全是为自己写的，应该只有作者本人可以看懂。。。不扯了，接下来借鉴了墙外的一些思路来写的。
　　当确定这个题可能要使用并查集的时候我们再来仔细分析一下要求，首先给定的是一段连续的自然数序列（或者数组下标）；第二点我们要获取移除的successor:　剩余数中大于数的队列中的最小数。我们来举个例子，
　　｛１ …8｝在这八个数中我们移除6，6的successor为7（find(6) ==7）；
　　再移除5，find(5) == 7；
　　再移除2 , find(2) == 3　find(3) = 3　find(5) ==7　
　　我们可以看到输出的值为一个连通域中最大值＋１，而这个连通域由我们remove（）的数组成。这就想起了上一道题，我们使用并查集来实现在对数时间中查找列表中的最大项。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class Successor {
    private int n;
    private boolean[] isRemove;
    private FindMax findMax;
    public Successor(int n){
        this.n = n; //大小为n的列表
        findMax = new FindMax();    //上一部分的FindMax类，提供union和find方法
        isRemove = new boolean[n];  //判断列表项中对应位置的数是否被移除
        for (int i = 0; i < isRemove.length; i++) {
            isRemove[i] = false;
        }
    }
    public void remove(int x) {
        isRemove[x] = true;
        if (x>0 && isRemove[x-1]){
            findMax.union(x,x-1);
        }else if (x<n-1 && isRemove[x+1]){
            findMax.union(x,x+1);
        }
    }
    public int getSuccessor(int x) {
        if(x<0 || x>n-1){   //输入不合法
            return -1;
        }else if(isRemove[x]){     //若是已经被移除的项,输出移除项中最大项+1
                return findMax.find(x)+1;
        }else {     //若不是移除项，则按照规则输出自己
            return x;
        }
    }
    public static void main(String[] args) {
        Successor successor = new Successor(8);
        successor.remove(3);
        successor.remove(2);
        successor.remove(0);
        successor.remove(4);
        successor.remove(7);
        System.out.println("the successor is : " + successor.getSuccessor(2));
    }
}

输出：

the successor is : 5

参考文章

http://vancexu.github.io/2015/07/21/intro-to-union-find-data-structure-exercise.html（墙内）