题解 | #明明的随机数#

思路: 利用一个 HashSet 实现输入的 N 个整数的去重功能，然后，对 剩余的数 进行排序。

排序有好多种方法，我一共用了 四种，仅供参考，谢谢!(Arrays包的内置排序、快速排序、归并排序、堆排序)

快速排序的代码实现

    public static void quickSort(int[] nums) {
        if (null == nums || nums.length < 2) {
            return;
        }
        process(nums, 0, nums.length - 1);
    }
    public static void process(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int l = start - 1;
        int r = end + 1;
        int p = start;
        int val = nums[end];
        while (p < r) {
            if (nums[p] < val) {
                swap(nums, p++, ++l);
            } else if (nums[p] > val) {
                swap(nums, p, --r);
            } else {
                p++;
            }
        }
        process(nums, start, l);
        process(nums, r, end);
    }
    public static void swap(int[] nums, int p1, int p2) {
        int tmp = nums[p1];
        nums[p1] = nums[p2];
        nums[p2] = tmp;
    }

归并排序的代码实现

    public static void mergeSort(int[] nums) {
        if (null == nums || nums.length < 2) {
            return;
        }
        process(nums, 0, nums.length - 1);
    }
    public static void process(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = start + ((end - start) >> 1);
        process(nums, start, mid);
        process(nums, mid + 1, end);
        merge(nums, start, mid, end);
    }
    public static void merge(int[] nums, int start, int mid, int end) {
        int[] helper = new int[end - start + 1];
        int index = 0;
        int p1 = start;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= end) {
            helper[index++] = nums[p1] <= nums[p2] ? nums[p1++] : nums[p2++];
        }
        while (p1 <= mid) {
            helper[index++] = nums[p1++];
        }
        while (p2 <= end) {
            helper[index++] = nums[p2++];
        }
        for (int i = 0; i < helper.length; i++) {
            nums[start + i] = helper[i];
        }
    }

堆排序的代码实现

    public static void heapSort(int[] nums) {
        if (null == nums || nums.length < 2) {
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            heapInsert(nums, i);
        }
        int heapSize = nums.length;
        swap(nums, 0, --heapSize);
        while (heapSize > 0) {
            heapify(nums, 0, heapSize);
            swap(nums, 0, --heapSize);
        }
    }
    public static void heapInsert(int[] nums, int index) {
        while (nums[index] > nums[(index - 1) / 2]) {
            swap(nums, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }
    public static void heapify(int[] nums, int index, int heapSize) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            int largest = left + 1 < heapSize && nums[left + 1] > nums[left] ? left + 1 : left;
            largest = nums[largest] > nums[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(nums, index, largest);
            index = largest;
            left = index * 2 + 1;
        }
    }
    public static void swap(int[] nums, int p1, int p2) {
        int tmp = nums[p1];
        nums[p1] = nums[p2];
        nums[p2] = tmp;
    }

整道题的完整代码如下

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String Nstr = scan.nextLine();
        int N = Integer.valueOf(Nstr.trim());
        HashSet<Integer> hashSet = new HashSet<>();
        for (int i = 1; i <= N; i++) {
            hashSet.add(Integer.valueOf(scan.nextLine().trim()));
        }
        int[] nums = new int[hashSet.size()];
        int index = 0;
        for (int num : hashSet) {
            nums[index++] = num;
        }
        Arrays.sort(nums); // 调用系统内置的排序方法
        // quickSort(nums); // 自己实现一个快速排序的算法，对数组进行排序
        // mergeSort(nums); // 自己实现一个归并排序的算法，对数组进行排序
        // heapSort(nums); // 自己实现一个堆排序的算法，对数据进行排序
        for (int num : nums) {
            System.out.println(num);
        }
    }
    /**********************************************************************************/
    // 快速排序
    /*
    public static void quickSort(int[] nums) {
        if (null == nums || nums.length < 2) {
            return;
        }
        process(nums, 0, nums.length - 1);
    }
    public static void process(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int l = start - 1;
        int r = end + 1;
        int p = start;
        int val = nums[end];
        while (p < r) {
            if (nums[p] < val) {
                swap(nums, p++, ++l);
            } else if (nums[p] > val) {
                swap(nums, p, --r);
            } else {
                p++;
            }
        }
        process(nums, start, l);
        process(nums, r, end);
    }
    public static void swap(int[] nums, int p1, int p2) {
        int tmp = nums[p1];
        nums[p1] = nums[p2];
        nums[p2] = tmp;
    }
    */
    /**********************************************************************************/
    // 归并排序
    /*
    public static void mergeSort(int[] nums) {
        if (null == nums || nums.length < 2) {
            return;
        }
        process(nums, 0, nums.length - 1);
    }
    public static void process(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = start + ((end - start) >> 1);
        process(nums, start, mid);
        process(nums, mid + 1, end);
        merge(nums, start, mid, end);
    }
    public static void merge(int[] nums, int start, int mid, int end) {
        int[] helper = new int[end - start + 1];
        int index = 0;
        int p1 = start;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= end) {
            helper[index++] = nums[p1] <= nums[p2] ? nums[p1++] : nums[p2++];
        }
        while (p1 <= mid) {
            helper[index++] = nums[p1++];
        }
        while (p2 <= end) {
            helper[index++] = nums[p2++];
        }
        for (int i = 0; i < helper.length; i++) {
            nums[start + i] = helper[i];
        }
    }
    */
    /**********************************************************************************/
    // 堆排序
    /*
    public static void heapSort(int[] nums) {
        if (null == nums || nums.length < 2) {
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            heapInsert(nums, i);
        }
        int heapSize = nums.length;
        swap(nums, 0, --heapSize);
        while (heapSize > 0) {
            heapify(nums, 0, heapSize);
            swap(nums, 0, --heapSize);
        }
    }
    public static void heapInsert(int[] nums, int index) {
        while (nums[index] > nums[(index - 1) / 2]) {
            swap(nums, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }
    public static void heapify(int[] nums, int index, int heapSize) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            int largest = left + 1 < heapSize && nums[left + 1] > nums[left] ? left + 1 : left;
            largest = nums[largest] > nums[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(nums, index, largest);
            index = largest;
            left = index * 2 + 1;
        }
    }
    public static void swap(int[] nums, int p1, int p2) {
        int tmp = nums[p1];
        nums[p1] = nums[p2];
        nums[p2] = tmp;
    }
    */
}