Java 9 ms merge sort solution, O(n log n), no library classes


  • -1

    This solution uses an optimized merge sort: copying is avoided when possible by alternating between source and destination arrays. When the part to sort had odd length an additional trick is used to ensure that the sorted data end up in one array instead of being distributed by different arrays due to different depth of recursion.

    It is verbose, but it runs in 9 ms, beat 87%. And it has guaranteed O(n log n) time.

    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums.length == 0)
            return false;
        int[] indices = new int[nums.length];
        for (int i = 0; i < nums.length; ++i) {
            indices[i] = i;
        }
        mergeSort(nums, indices);
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i - 1] == nums[i] && Math.abs(indices[i - 1] - indices[i]) <= k)
                return true;
        }
        return false;
    }
    
    public static void mergeSort(int[] nums, int[] indices) {
        int[] auxNums = new int[nums.length];
        int[] auxIndices = new int[indices.length];
        boolean moved = mergeSort(nums, indices, 0, nums.length,
                auxNums, auxIndices, false);
        if (moved) {
            System.arraycopy(auxNums, 0, nums, 0, nums.length);
            System.arraycopy(auxIndices, 0, indices, 0, indices.length);
        }
    }
    
    /**
     * Performs a merge sort.
     * 
     * @param nums source numbers
     * @param indices source indices
     * @param start the beginning of the region to sort (inclusive)
     * @param end the end of the region to sort (exclusive)
     * @param auxNums the helper array for numbers
     * @param auxIndices the helper array for indices
     * @param wantToMove whether it's preferable to have the result in the aux arrays
     * @return whether the result is in the aux arrays
     */
    private static boolean mergeSort(int[] nums, int[] indices, int start, int end,
            int[] auxNums, int[] auxIndices, boolean wantToMove) {
        if (end - start >= 2) {
            int mid = start + (end - start) / 2;
            boolean movedLeft, movedRight;
            if ((mid - start) % 2 == (end - mid) % 2) {
                // Both even or both odd, no special preference.
                movedLeft = mergeSort(nums, indices, start, mid, auxNums,
                    auxIndices, !wantToMove);
                movedRight = mergeSort(nums, indices, mid, end, auxNums,
                    auxIndices, !wantToMove);
            } else if ((mid - start) % 2 == 0) {
                // Even, odd.
                movedLeft = mergeSort(nums, indices, start, mid, auxNums,
                    auxIndices, !wantToMove);
                movedRight = mergeSort(nums, indices, mid, end, auxNums,
                    auxIndices, movedLeft);
            } else {
                // Odd, even.
                movedRight = mergeSort(nums, indices, mid, end, auxNums,
                    auxIndices, !wantToMove);
                movedLeft = mergeSort(nums, indices, start, mid, auxNums,
                    auxIndices, movedRight);
            }
            assert movedRight == movedLeft;
            if (movedLeft) {
                merge(auxNums, auxIndices, nums, indices, start, end);
            } else {
                merge(nums, indices, auxNums, auxIndices, start, end);
            }
            return !movedLeft; // If we moved, then merge moved back.
        } else {
            if (wantToMove) {
                if (end - start == 1) {
                    auxNums[start] = nums[start];
                    auxIndices[start] = indices[start];
                }
                return true;
            } else {
                return false;
            }
        }
    }
    
    private static void merge(int[] srcNums, int[] srcIndicies,
            int[] destNums, int[] destIndicies, int start, int end) {
        int mid = start + (end - start) / 2;
        int i = start, j = mid, k = start;
        while (i < mid || j < end) {
            if (i < mid && j < end) {
                if (lt(srcNums, srcIndicies, i, j)) {
                    destNums[k++] = srcNums[i++];
                    destIndicies[k - 1] = srcIndicies[i - 1];
                } else {
                    destNums[k++] = srcNums[j++];
                    destIndicies[k - 1] = srcIndicies[j - 1];
                }
            } else if (i < mid) {
                destNums[k++] = srcNums[i++];
                destIndicies[k - 1] = srcIndicies[i - 1];
            } else { // j < mid
                destNums[k++] = srcNums[j++];
                destIndicies[k - 1] = srcIndicies[j - 1];
            }
        }
    }
    
    private static boolean lt(int[] nums, int[] indices, int i, int j) {
        if (nums[i] < nums[j]) {
            return true;
        } else if (nums[i] > nums[j]) {
            return false;
        } else {
            return indices[i] < indices[j];
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.