0

我尝试使用“随机枢轴”方法在给定数组中找到第 K 个最小元素。
[编码]

public class FindKthMin {

// Find the Kth min elem by randomized pivot.
private static void exchange (int[] givenArray, int firstIndex, int secondIndex) {
    int tempElem = givenArray[firstIndex];
    givenArray[firstIndex] = givenArray[secondIndex];
    givenArray[secondIndex] = tempElem;
}
private static int partition (int[] givenArray, int start, int end, int pivotIndex) {

    // Debug:
    //System.out.println("debug: start = " + start);
    //System.out.println(">> end = " + end);
    //System.out.println(">> pivotIndex = " + pivotIndex);


    int pivot = givenArray[pivotIndex];
    int left = start - 1;
    int right = end;
    boolean hasDone = false;
    while (!hasDone) {
        while (!hasDone) {
            left ++;
            if (left == right) {
                hasDone = true;
                break;
            }
            if (givenArray[left] >= pivot) {
                // Exchange givenArray[left] and the givenArray[right].
                exchange(givenArray, left, right);
                break;
            }
        }
        while (!hasDone) {
            right --;
            if (left == right) {
                hasDone = true;
                break;
            }
            if (givenArray[right] < pivot) {
                // Exchange the givenArray[right] and the givenArray[left].
                exchange(givenArray, right, left);
                break;
            }
        }
    }
    givenArray[right] = pivot;
    // Debug:
    //System.out.println(">> split = " + right);
    //System.out.println();
    return right;
}
private static int findKthMin_RanP_Helper (int[] givenArray, int start, int end, int k) {
    if (start > end) return -1;
    // Generate a random num in the range[start, end].
    int rand = (int)(start +  Math.random() * (end - start + 1));
    // Using this random num as the pivot index to partition the array in the current scope.
    int split = partition(givenArray, start, end, rand);
    if (k == split + 1) return givenArray[split];
    else if (k < split + 1) return findKthMin_RanP_Helper(givenArray, start, split - 1, k);
    else return findKthMin_RanP_Helper(givenArray, split + 1, end, k);
}
public static int findKthMin_RanP (int[] givenArray, int k) {
    int size = givenArray.length;
    if (k < 1 || k > size) return -1;
    return findKthMin_RanP_Helper(givenArray, 0, size - 1, k);
}


// Main method to test.
public static void main (String[] args) {
    // Test data: {8, 9, 5, 2, 8, 4}.
    int[] givenArray = {8, 9, 5, 2, 8, 4};

    // Test finding the Kth min elem by randomized pivot method.
    System.out.println("Test finding the Kth min elem by randomized pivot method, rest = " + findKthMin_RanP(givenArray, 1));
}
}

但结果是不稳定的，有时对有时错。
请看一下findKthMin_RanP_Helper方法的第 5 行：
如果我把它改成int split = partition(givenArray, start, end, rand);，int split = partition(givenArray, start, end, end);结果总是正确的。
我真的找不到这有什么问题。

编辑：
问题来自“分区”，新分区应该是这样的： 

    private static int partition_second_version (int[] givenArray, int start, int end, int pivotIndex) {
    int pivot = givenArray[pivotIndex];
    int left = start;
    int right = end;
    while (left <= right) {
        while (givenArray[left] < pivot) left ++;
        while (givenArray[right] > pivot) right --;
        if (left <= right) {
            // Exchange givenArray[left] and givenArray[right].
            exchange(givenArray, left, right);
            left ++;
            right --;
        }
    }
    return left;
}


并且findKthMin_RanP_Helper应该像这样更改：

    private static int findKthMin_RanP_Helper (int[] givenArray, int start, int end, int k) {
    if (start > end) return -1;
    // Generate a random num in the range[start, end].
    int rand = start +  (int)(Math.random() * ((end - start) + 1));
    // Using this random num as the pivot index to partition the array in the current scope.
    int split = partition_second_version (givenArray, start, end, rand);
    if (k == split) return givenArray[split - 1];
    else if (k < split) return findKthMin_RanP_Helper(givenArray, start, split - 1, k);
    else return findKthMin_RanP_Helper(givenArray, split, end, k);
}
4

1 回答 1

1

您的分区程序可以简化...

  private static int partition(int[] givenArray, int start, int end, int pivotIndex) {
    final int pivot = givenArray[pivotIndex];
    int left = start;
    int right = end;
    while (left < right) {
        while (left < givenArray.length && givenArray[left] <= pivot) {
            left++;
        }

        while (right > -1 && givenArray[right] > pivot) {
            right--;
        }

        if (left >= right) {
            break;
        }
        exchange(givenArray, right, left);
    }
    return right;
}

我在您的代码中看到的一个错误是您的分区例程。在第一次交换调用中，不能保证正确的索引总是指向一个 < pivot 的值。

于 2014-04-07T05:16:45.310 回答