狗家电面

今天刚面。
给一个array of objects,求second largest object。object 有自定义的 compare function ,而且compare的消耗非常大,所以要尽量减少比较的次数。

一开始我说sort by ascending order,然后取倒数第二个不就完了,那边说不是最优。
然后写了类似于 https://stackoverflow.com/questi … m-array-efficiently 的解法。

之后那边说还能不能再提升,提示之后是 divide and conquer,只说了思路,类似于 https://www.8bitavenue.com/2010/ … divide-and-conquer/
算出来的复杂度确实能减少一些对于compare的调用。

用selection algorithm会不会好一些,类似于quick sort那种的,quick select

priorityqueue?

只考虑worst case

祝你成功

/**
 * Java version
 * divide and conquer with O(n) time complexity and minimum compare times
 */
public class DivideAndConquerToFindSecondLargest {
    static class Result {
        int max1;
        int max2;

        Result(int max1, int max2) {
            this.max1 = max1;
            this.max2 = max2;
        }
    }
    public static void main(String[] args) {
        int[] A = {1, 5, 2, 4, 3};

        // Find first and second max elements
        Result res = FirstSecondMax(A, 0, 4);

        System.out.println("First one is : " + res.max1);
        System.out.println("Second one is : " + res.max2);
    }

    private static Result FirstSecondMax(int[] A, int l, int r) {
        Result res = new Result(A[l], A[r]);

        // if array has only one element return null record
        if (l == r) {
            return res;
        }

        // Base case when array has only two elements
        if (r - l == 1) {
            // if right element is greater than the left one
            // then right one is the first maximum
            if (A[r] >= A[l]) {
                res.max1 = A[r];
                res.max2 = A[l];
            } else {
                res.max1 = A[l];
                res.max2 = A[r];
            }
            return res;
        }

        // Find middle element
        int m = (l + r) / 2;

        // find the largest two elements in each half
        Result lres = FirstSecondMax(A, l, m);
        Result rres = FirstSecondMax(A, m + 1, r);

        // so far we got 4 max values 2 on each half
        // so we need to merge them and take out only two

        // First max on the right is greater than first max on the left
        if (rres.max1 >= lres.max1) {
            // Take the first max on the right
            res.max1 = rres.max1;

            // Compare second max on the right with first max on the left
            if (rres.max2 >= lres.max1) {
                res.max2 = rres.max2;
            } else {
                res.max2 = lres.max1;
            }
        } else {
            // First max on the left is greater that first max on the right
            res.max1 = lres.max1;

            // compare second max on the left with first max on the right
            if (lres.max2 >= rres.max1) {
                res.max2 = lres.max2;
            } else {
                res.max2 = rres.max1;
            }
        }
        return res;
    }
}

这不就是我给的链接里面的?

这也太难了吧