這是悅樂書的第207次更新，第219篇原創(chuàng)

01 看題和準(zhǔn)備

今天介紹的是LeetCode算法題中Easy級(jí)別的第75題（順位題號(hào)是349）。給定兩個(gè)數(shù)組，編寫一個(gè)函數(shù)來計(jì)算它們的交集。例如：

輸入：nums1 = [1,2,2,1]，nums2 = [2,2]
輸出：[2]

輸入：nums1 = [4,9,5]，nums2 = [9,4,9,8,4]
輸出：[9,4]

注意：

• 結(jié)果中的每個(gè)元素都必須是唯一的。

• 結(jié)果可以是任何順序。

本次解題使用的開發(fā)工具是eclipse，jdk使用的版本是1.8，環(huán)境是win7 64位系統(tǒng)，使用Java語言編寫和測(cè)試。

02 第一種解法

暴力解法，直接使用兩層循環(huán)，依次比較兩個(gè)數(shù)組中的元素，如果相等，則將其存入HashSet中，這樣可以保證不會(huì)出現(xiàn)重復(fù)元素，再將HashSet中的元素迭代放入數(shù)組，最后返回該數(shù)組。

此解法的時(shí)間復(fù)雜度是O(n^2)，空間復(fù)雜度是O(n)。

public int[] intersection(int[] nums1, int[] nums2) {
    Set<Integer> set = new HashSet<Integer>();
    for(int i=0; i<nums1.length; i++){
        int tem = nums1[i];
        for (int j=0; j<nums2.length; j++) {
            if (tem == nums2[j]) {
                set.add(tem);
                break;
            }
        }
    }
    int[] result = new int[set.size()];
    int k = 0;
    for (int num : set) {
        result[k++] = num;
    }
    return result;
}

03 第二種解法

使用兩個(gè)HashSet，先將其中一個(gè)數(shù)組的元素全部放入第一個(gè)HashSet中，然后迭代第二個(gè)數(shù)組，先判斷第二個(gè)數(shù)組的每一個(gè)元素是否存在于第一個(gè)HashSet中，如果存在，將其放入第二個(gè)HashSet中，然后將第二個(gè)HashSet的元素迭代放入新數(shù)組中，最后返回。

此解法因?yàn)橛玫搅薍ashSet的contains方法，因此時(shí)間復(fù)雜度最好情況是O(n)，最壞情況是O(n^2)，空間復(fù)雜度是O(n)。

public int[] intersection2(int[] nums1, int[] nums2) {
    Set<Integer> intersection = new HashSet<Integer>();
    Set<Integer> set = new HashSet<Integer>();
    for (int i : nums1) {
        set.add(i);
    }
    for (int i : nums2) {
        if (set.contains(i)) {
            intersection.add(i);
        }
    }
    int[] answer = new int[intersection.size()];
    int index = 0;
    for (int i : intersection) {
        answer[index++] = i;
    }
    return answer;
}

04 第三種解法

先將兩數(shù)組排序，然后使用雙指針，依次判斷兩數(shù)組中的元素是否相等，如果某個(gè)元素大于或小于另外一個(gè)元素，則將指針向后移動(dòng)，如果相等，則將元素放入HashSet中，然后將HashSet中的元素迭代放入數(shù)組，最后返回。

因?yàn)槭褂肁rrays類的sort方法，所以時(shí)間復(fù)雜度是O(n log(n))，空間復(fù)雜度是O(n)。

public int[] intersection3(int[] nums1, int[] nums2) {
    Set<Integer> set = new HashSet<>();
    Arrays.sort(nums1);
    Arrays.sort(nums2);
    int i = 0;
    int j = 0;
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] < nums2[j]) {
            i++;
        } else if (nums1[i] > nums2[j]) {
            j++;
        } else {
            set.add(nums1[i]);
            i++;
            j++;
        }
    }
    int[] result = new int[set.size()];
    int k = 0;
    for (Integer num : set) {
        result[k++] = num;
    }
    return result;
}

05 第四種解法

此解法和第一種解法類似，只是將內(nèi)層循環(huán)換成了二分查找法，其他的思路都是一樣的。

此解法的時(shí)間復(fù)雜度是O(nlogn)，空間復(fù)雜度是O(n)。

public int[] intersection4(int[] nums1, int[] nums2) {
    Set<Integer> set = new HashSet<>();
    Arrays.sort(nums2);
    for (Integer num : nums1) {
        if (binarySearch(nums2, num)) {
            set.add(num);
        }
    }
    int i = 0;
    int[] result = new int[set.size()];
    for (Integer num : set) {
        result[i++] = num;
    }
    return result;
}

public boolean binarySearch(int[] nums, int target) {
    int low = 0;
    int high = nums.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] == target) {
            return true;
        }
        if (nums[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return false;
}

06 小結(jié)

算法專題目前已連續(xù)日更超過兩個(gè)月，算法題文章75+篇，公眾號(hào)對(duì)話框回復(fù)【數(shù)據(jù)結(jié)構(gòu)與算法】、【算法】、【數(shù)據(jù)結(jié)構(gòu)】中的任一關(guān)鍵詞，獲取系列文章合集。

以上就是全部內(nèi)容，如果大家有什么好的解法思路、建議或者其他問題，可以下方留言交流，點(diǎn)贊、留言、轉(zhuǎn)發(fā)就是對(duì)我最大的回報(bào)和支持！