給定兩個(gè)數(shù)組据途，寫一個(gè)函數(shù)來(lái)計(jì)算它們的交集绰播。

例子:
給定 num1= [1, 2, 2, 1], nums2 = [2, 2], 返回 [2].

提示:
每個(gè)在結(jié)果中的元素必定是唯一的聚唐。
我們可以不考慮輸出結(jié)果的順序洛史。

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        // 元素唯一秘豹，考慮使用 Set 的特性
        // 因?yàn)榭梢圆豢紤]輸出結(jié)果的順序，所以可以先對(duì)數(shù)組排序术浪，然后再比較兩個(gè)數(shù)組瓢对，遇到已有結(jié)果的相同的數(shù)據(jù)可以跳過(guò)，減少不必要的比較
        
        if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) {
            return new int[0];
        }
    
        // 對(duì)數(shù)組進(jìn)行快排
        quickSort(nums1, 0, nums1.length - 1);
        quickSort(nums2, 0, nums2.length - 1);
        
        // Arrays.sort(nums1); 
        //  Arrays.sort(nums2);
       
        int[] resultT = new int[nums1.length < nums2.length ? nums1.length : nums2.length];
        int n = 0;
        int i = 0;
        int j = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] == nums2[j]) {
                if (n == 0 || resultT[n - 1] != nums1[i]) {
                    resultT[n] = nums1[i];
                    n++;
                }
            
                ++i;
                ++j;
            } else if (nums1[i] < nums2[j]) {
                ++i;
            } else {
                ++j;
            }
        }
        
        int[] result = new int[n];
        while (--n >= 0) {
            result[n] = resultT[n];
        }
        
        return result;
    }
    
    private static void quickSort(int[] nums, int start, int end) {
        if (nums == null || nums.length < 2 || start >= end) {
            return;
        }
    
        int i = start, j = end;
        // 選一個(gè)基準(zhǔn)值胰苏，完成一次快排操作后，數(shù)組序列在該值可分為左右兩個(gè)部分醇疼，在其左邊的序列都比該基準(zhǔn)值小硕并，在其右邊的序列都比該基準(zhǔn)值大
        int pivot = nums[(start + end) / 2];
        while (i <= j) {
            // 夾逼原則，分別從左右開端進(jìn)行判斷
            while(i <= j && nums[i] < pivot) { // 從左邊開始秧荆，比基準(zhǔn)值小的直接跳過(guò)
                ++i; 
            }
            
            while(i <= j && nums[j] > pivot) { // 從有邊開始倔毙，比基準(zhǔn)值大的直接跳過(guò)
                --j;
            }
            
            if (i < j) { // 此時(shí)肯定是出現(xiàn)左邊的數(shù)了大于或等于基準(zhǔn)值或者右邊數(shù)小于或等于基準(zhǔn)值的情況，需要交換兩者位置
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                ++i;
                --j;
            } else if (i == j) {
                // 如果 i = j 說(shuō)明已經(jīng)到了數(shù)組中間乙濒，一次快排結(jié)束陕赃，i + 1 滿足跳出循環(huán)的條件
                ++i;
            }
        }
        
        // 左右兩個(gè)子序列進(jìn)行遞歸調(diào)用
        quickSort(nums, start, j);
        quickSort(nums, i, end);
    }
}