java - 显示快速查找数组

Question

我正在尝试打印出完整的数组 id[]在每次 union() 之后方法被调用。在main()方法。还需要蜜蜂能够计算访问数组的次数。我知道在调用连接方法时访问了两次，在调用 find() 时访问了一次。直到 2n + 1打电话时 union() .请帮忙。

    public class QuickFindUF {
private int[] id;    // id[i] = component identifier of i
private int count; // number of components

/**
 * Initializes an empty union–find data structure with {@code n} sites
 * {@code 0} through {@code n-1}. Each site is initially in its own 
 * component.
 *
 * @param  n the number of sites
 * @throws IllegalArgumentException if {@code n < 0}
 */
public QuickFindUF(int n) {
    count = n;
    id = new int[n];
    for (int i = 0; i < n; i++)
        id[i] = i;
}

/**
 * Returns the number of components.
 *
 * @return the number of components (between {@code 1} and {@code n})
 */
public int count() {
    return count;
}


/**
 * Returns the component identifier for the component containing site {@code p}.
 *
 * @param  p the integer representing one site
 * @return the component identifier for the component containing site {@code p}
 * @throws IndexOutOfBoundsException unless {@code 0 <= p < n}
 */
public int find(int p) {
    validate(p);

    return id[p];
}

// validate that p is a valid index
private void validate(int p) {
    int n = id.length;
    if (p < 0 || p >= n) {
        throw new IndexOutOfBoundsException("index " + p + " is not between 0 and " + (n-1));
    }
}

/**
 * Returns true if the the two sites are in the same component.
 *
 * @param  p the integer representing one site
 * @param  q the integer representing the other site
 * @return {@code true} if the two sites {@code p} and {@code q} are in the same component;
 *         {@code false} otherwise
 * @throws IndexOutOfBoundsException unless
 *         both {@code 0 <= p < n} and {@code 0 <= q < n}
 */
public boolean connected(int p, int q) {
    validate(p);
    validate(q);

    return id[p] == id[q];
}

/**
 * Merges the component containing site {@code p} with the 
 * the component containing site {@code q}.
 *
 * @param  p the integer representing one site
 * @param  q the integer representing the other site
 * @throws IndexOutOfBoundsException unless
 *         both {@code 0 <= p < n} and {@code 0 <= q < n}
 */
public void union(int p, int q) {
    validate(p);
    validate(q);
    int pID = id[p];   // needed for correctness
    int qID = id[q];   // to reduce the number of array accesses

    // p and q are already in the same component
    if (pID == qID)

        return;

    for (int i = 0; i < id.length; i++)
        if (id[i] == pID) id[i] = qID;
    count--;

}

/**
 * Reads in a sequence of pairs of integers (between 0 and n-1) from standard input, 
 * where each integer represents some site;
 * if the sites are in different components, merge the two components
 * and print the pair to standard output.
 *
 * @param args the command-line arguments
 */
public static void main(String[] args) {
    int n = StdIn.readInt();
    QuickFindUF uf = new QuickFindUF(n);
    while (!StdIn.isEmpty()) {
        int p = StdIn.readInt();
        int q = StdIn.readInt();

        if (uf.connected(p, q)){
            continue;
        }
        uf.union(p, q);
        StdOut.println(p + " " + q);
    }
    StdOut.println(uf.count() + " components");

}

     }

Answer 1

正在尝试分解您的问题...

第 1 部分:

I'm trying to print out the full array id[] after each time the union method is called. in the main method.

尝试创建一个字符串缓冲区并在访问它时添加元素。一旦你完成并想打印数组，你可以只打印字符串缓冲区..

public void union(int p, int q) {
    validate(p);
    validate(q);
    int pID = id[p];   // needed for correctness
    int qID = id[q];   // to reduce the number of array accesses

    // p and q are already in the same component
    if (pID == qID)

        return;

    StringBuilder sb=new StringBuilder("");  

    for (int i = 0; i < id.length; i++)
    {
        sb.append(id[i]) + " "; // you are accessing all id elements anyway; add it to the 'sb' string while you are at it
                                // seperate each id element with a space
                                // do it in this place (before the if statement below) if you would like to print the before state of the array

        if (id[i] == pID) 
            id[i] = qID;

        //sb.append(id[i]) + " ";  // do it here if you would like to print the after state of the array

    }

    System.out.println(sb);
    count--;

}

第 2 部分:

also need to bee able to count the number of times the array is accessed. i am aware that it is accessed twice when calling the connected method, once when calling find() and up to 2n + 1 when calling union()

为此你需要考虑重构你的代码..因为你在同一个类中处理数组，你将无法计算你访问这个数组的次数..但是你可以考虑将数组放在一个不同的类作为私有(private)变量。通过 getter 和/或 setter 方法创建访问点。然后你可以计算你以可靠的方式访问数组的次数..

希望这有帮助..