leetcode_排列_簡單

重新排列字元串

連結：https://leetcode-cn.com/problems/shuffle-string

給你一個字元串 s 和一個 長度相同 的整數數組 indices 。

請你重新排列字元串 s ，其中第 i 個字元需要移動到 indices[i] 訓示的位置。

傳回重新排列後的字元串。

示例 1：

輸入：s = “codeleet”, indices = [4,5,6,7,0,2,1,3]

輸出：“leetcode”

解釋：如圖所示，“codeleet” 重新排列後變為 “leetcode” 。

示例 2：

輸入：s = “abc”, indices = [0,1,2]

輸出：“abc”

解釋：重新排列後，每個字元都還留在原來的位置上。

示例 3：

輸入：s = “aiohn”, indices = [3,1,4,2,0]

輸出：“nihao”

示例 4：

輸入：s = “aaiougrt”, indices = [4,0,2,6,7,3,1,5]

輸出：“arigatou”

示例 5：

輸入：s = “art”, indices = [1,0,2]

輸出：“rat”

提示：

s.length == indices.length == n

1 <= n <= 100

s 僅包含小寫英文字母。

0 <= indices[i] < n

indices 的所有的值都是唯一的（也就是說，indices 是整數 0 到 n - 1 形成的一組排列）。

解題思路：

（我）

class Solution {
    public String restoreString(String s, int[] indices) {
        char[] chars = s.toCharArray();
        char[] chars1 = new char[chars.length];
        StringBuilder stringBuilder = new StringBuilder();
        for (int i=0;i<chars.length;i++){
            chars1[indices[i]] = chars[i];
        }
        for (Character character:chars1) {
            stringBuilder.append(character);
        }
        return stringBuilder.toString();
    }
}
           

（官方）

class Solution {
    public String restoreString(String s, int[] indices) {
        int length = s.length();
        char[] result = new char[length];

        for (int i = 0; i < length; i++) {
            result[indices[i]] = s.charAt(i);
        }
        return new String(result);
    }
}
           

判斷能否形成等差數列

連結：https://leetcode-cn.com/problems/can-make-arithmetic-progression-from-sequence

給你一個數字數組 arr 。

如果一個數列中，任意相鄰兩項的差總等于同一個常數，那麼這個數列就稱為 等差數列 。

如果可以重新排列數組形成等差數列，請傳回 true ；否則，傳回 false 。

示例 1：

輸入：arr = [3,5,1]

輸出：true

解釋：對數組重新排序得到 [1,3,5] 或者 [5,3,1] ，任意相鄰兩項的差分别為 2 或 -2 ，可以形成等差數列。

示例 2：

輸入：arr = [1,2,4]

輸出：false

解釋：無法通過重新排序得到等差數列。

提示：

2 <= arr.length <= 1000

-10^6 <= arr[i] <= 10^6

解題思路：

（我）

class Solution {
    public boolean canMakeArithmeticProgression(int[] arr) {
        boolean flag=true;
        int temp;
        for (int i=0;i<arr.length-1;i++){
            int k=i;
            for (int j=i+1;j<arr.length;j++){
                if (arr[j] <arr[k]){
                    k =j;
                }
            }
            if (i!=k){
                temp = arr[i];
                arr[i] = arr[k];
                arr[k] = temp;
            }
        }
        System.out.println(Arrays.toString(arr));
        for (int m=1;m<arr.length-1;m++){
            if (arr[m + 1] + arr[m - 1] != arr[m] * 2) {
                flag = false;
                break;
            }
        }
        return flag;
    }
}
           

（官方）

class Solution {
    public boolean canMakeArithmeticProgression(int[] arr) {
        Arrays.sort(arr);
        for (int i = 1; i < arr.length - 1; ++i) {
            if (arr[i] * 2 != arr[i - 1] + arr[i + 1]) {
                return false;
            }
        }
        return true;
    }
}
           

去掉最低工資和最高工資後的工資平均值

連結：https://leetcode-cn.com/problems/average-salary-excluding-the-minimum-and-maximum-salary

給你一個整數數組 salary ，數組裡每個數都是 唯一 的，其中 salary[i] 是第 i 個員工的工資。

請你傳回去掉最低工資和最高工資以後，剩下員工工資的平均值。

示例 1：

輸入：salary = [4000,3000,1000,2000]

輸出：2500.00000

解釋：最低工資和最高工資分别是 1000 和 4000 。

去掉最低工資和最高工資以後的平均工資是 (2000+3000)/2= 2500

示例 2：

輸入：salary = [1000,2000,3000]

輸出：2000.00000

解釋：最低工資和最高工資分别是 1000 和 3000 。

去掉最低工資和最高工資以後的平均工資是 (2000)/1= 2000

示例 3：

輸入：salary = [6000,5000,4000,3000,2000,1000]

輸出：3500.00000

示例 4：

輸入：salary = [8000,9000,2000,3000,6000,1000]

輸出：4750.00000

提示：

3 <= salary.length <= 100

10^3 <= salary[i] <= 10^6

salary[i] 是唯一的。

與真實值誤差在 10^-5 以内的結果都将視為正确答案。

解題思路：

（我）

class Solution {
    public double average(int[] salary) {
        double d=0;
        for (int i=0;i<salary.length-1;i++){
            int k=i;
            for (int j=i+1;j<salary.length;j++){
                if (salary[k] >salary[j]){
                    k =j;
                }
            }
            if (i!=k){
                int temp = salary[i];
                salary[i] = salary[k];
                salary[k] =temp;
            }
        }
        for (int m=1;m<salary.length-1;m++){
            d += salary[m];
        }
        return d/(salary.length-2);
    }
}
           

（官方）

class Solution {
    public double average(int[] salary) {
        double sum = 0;
        double maxValue = Integer.MIN_VALUE, minValue = Integer.MAX_VALUE;
        for (int num : salary) {
            sum += num;
            maxValue = Math.max(maxValue, num);
            minValue = Math.min(minValue, num);
        }
        return (sum - maxValue - minValue) / (salary.length - 2);
    }
}
           

根據數字二進制下1的數目排序

連結：https://leetcode-cn.com/problems/sort-integers-by-the-number-of-1-bits

給你一個整數數組 arr 。請你将數組中的元素按照其二進制表示中數字 1 的數目升序排序。

如果存在多個數字二進制中 1 的數目相同，則必須将它們按照數值大小升序排列。

請你傳回排序後的數組。

示例 1：

輸入：arr = [0,1,2,3,4,5,6,7,8]

輸出：[0,1,2,4,8,3,5,6,7]

解釋：[0] 是唯一一個有 0 個 1 的數。

[1,2,4,8] 都有 1 個 1 。

[3,5,6] 有 2 個 1 。

[7] 有 3 個 1 。

按照 1 的個數排序得到的結果數組為 [0,1,2,4,8,3,5,6,7]

示例 2：

輸入：arr = [1024,512,256,128,64,32,16,8,4,2,1]

輸出：[1,2,4,8,16,32,64,128,256,512,1024]

解釋：數組中所有整數二進制下都隻有 1 個 1 ，是以你需要按照數值大小将它們排序。

示例 3：

輸入：arr = [10000,10000]

輸出：[10000,10000]

示例 4：

輸入：arr = [2,3,5,7,11,13,17,19]

輸出：[2,3,5,17,7,11,13,19]

示例 5：

輸入：arr = [10,100,1000,10000]

輸出：[10,100,10000,1000]

提示：

1 <= arr.length <= 500

0 <= arr[i] <= 10^4

解題思路：

（我）

class Solution {
public int[] sortByBits(int[] arr) {
        int[] sizes = new int[arr.length];
        for (int j=0;j<arr.length;j++){
            for (int k=1;k<arr.length-j;k++){
                if (arr[k] <arr[k-1]){
                    int temp = arr[k];
                    arr[k] = arr[k-1];
                    arr[k-1]=temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));

        for (int i=0;i<arr.length;i++){
            int arr1 = arr[i];
            int size=0;
            while (arr1/2!=0){
                if (arr1%2==1){
                    size+=1;
                }
                arr1 = arr1/2;
            }
            sizes[i]=size;
        }
        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(sizes));
        for (int m=0;m<sizes.length;m++){
            for (int o=1;o<sizes.length-m;o++){
                if (sizes[o] <sizes[o-1]){
                    int a= sizes[o];
                    sizes[o] = sizes[o-1];
                    sizes[o-1]=a;
                    int b=arr[o];
                    arr[o] = arr[o-1];
                    arr[o-1] =b;
                }
            }
        }
        System.out.println(Arrays.toString(sizes));
        return arr;
    }
}
           

（官方）

數組的相對排序

連結：https://leetcode-cn.com/problems/relative-sort-array

給你兩個數組，arr1 和 arr2，

arr2 中的元素各不相同

arr2 中的每個元素都出現在 arr1 中

對 arr1 中的元素進行排序，使 arr1 中項的相對順序和 arr2 中的相對順序相同。未在 arr2 中出現過的元素需要按照升序放在 arr1 的末尾。

示例：

輸入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]

輸出：[2,2,2,1,4,3,3,9,6,7,19]

提示：

arr1.length, arr2.length <= 1000

0 <= arr1[i], arr2[i] <= 1000

arr2 中的元素 arr2[i] 各不相同

arr2 中的每個元素 arr2[i] 都出現在 arr1 中

解題思路：

（我）

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        Map<Integer, Integer> map = new HashMap<>();
        List<Integer> arr3 = new ArrayList<>();
        List<Integer> arr4 = new ArrayList<>();
        int m = 0,n=0;
        for (int i=0;i<arr2.length;i++){
            map.put(arr2[i], i);
        }
        for (int i : arr1) {
            if (!map.containsKey(i)) {
                arr4.add(m, i);
                m++;
            } else {
                arr3.add(n, i);
                n++;
            }
        }
        System.out.println(arr4);
        System.out.println(arr3);
        for (int a=0;a<arr3.size();a++){
            for (int b=1;b<arr3.size()-a;b++){
                if (map.get(arr3.get(b))<map.get(arr3.get(b-1))){
                    int temp1= arr3.get(b);
                    arr3.set(b, arr3.get(b-1));
                    arr3.set(b-1, temp1);
                }
            }
        }
        System.out.println(arr3);
        for (int q=0;q<arr4.size()-1;q++){
            int k=q;
            for (int p=q+1;p<arr4.size();p++){
                if (arr4.get(p) <arr4.get(k)){
                    k=p;
                }
            }
            if (k!=q){
                int temp2 = arr4.get(q);
                arr4.set(q, arr4.get(k));
                arr4.set(k, temp2);
            }
        }
        System.out.println(arr4);

        Object[] result = Arrays.copyOf(arr3.toArray(), arr3.size() + arr4.size());
        System.arraycopy(arr4.toArray(), 0, result, arr3.size(), arr4.size());
        int[] arr5 = new int[result.length];
        int x=0;
        for (Object r:result){
            arr5[x] = Integer.parseInt(r.toString());
            x++;
        }
        return arr5;
    }
}
           

（官方）

無

距離順序排列矩陣單元格

連結：https://leetcode-cn.com/problems/matrix-cells-in-distance-order

給出 R 行 C 列的矩陣，其中的單元格的整數坐标為 (r, c)，滿足 0 <= r < R 且 0 <= c < C。

另外，我們在該矩陣中給出了一個坐标為 (r0, c0) 的單元格。

傳回矩陣中的所有單元格的坐标，并按到 (r0, c0) 的距離從最小到最大的順序排，其中，兩單元格(r1, c1) 和 (r2, c2) 之間的距離是曼哈頓距離，|r1 - r2| + |c1 - c2|。（你可以按任何滿足此條件的順序傳回答案。）

示例 1：

輸入：R = 1, C = 2, r0 = 0, c0 = 0

輸出：[[0,0],[0,1]]

解釋：從 (r0, c0) 到其他單元格的距離為：[0,1]

示例 2：

輸入：R = 2, C = 2, r0 = 0, c0 = 1

輸出：[[0,1],[0,0],[1,1],[1,0]]

解釋：從 (r0, c0) 到其他單元格的距離為：[0,1,1,2]

[[0,1],[1,1],[0,0],[1,0]] 也會被視作正确答案。

示例 3：

輸入：R = 2, C = 3, r0 = 1, c0 = 2

輸出：[[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]

解釋：從 (r0, c0) 到其他單元格的距離為：[0,1,1,2,2,3]

其他滿足題目要求的答案也會被視為正确，例如 [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]]。

提示：

1 <= R <= 100

1 <= C <= 100

0 <= r0 < R

0 <= c0 < C

解題思路：

（我）

class Solution {
    public int[][] allCellsDistOrder(int R, int C, int r0, int c0) {
        int[][] array4 = new int[R*C][2];
        List<List<Integer>> array3 = new ArrayList<>();
        List<Integer> array1, array;
        int size, m=0;
        Map<List<Integer>, Integer> map = new HashMap<>();
        for (int i=0;i<R;i++){
            for (int j=0;j<C;j++){
                array = new ArrayList<>();
                array.add(i);
                array.add(j);
                array3.add(array);
                array1 = new ArrayList<>();
                array1.add(i);
                array1.add(j);
                size = Math.abs(i-r0) + Math.abs(j-c0);
                map.put(array1, size);
            }
        }
        quickSort(array3, map);
        for (Object o:array3.toArray()) {
            List<Integer> list = new ArrayList<>();
            if (o instanceof ArrayList<?>){
                for (Object object : (List<?>) o){
                    list.add((Integer) object);
                }
            }
            int[] arr = new int[list.size()];
            for (int n=0;n<list.size();n++){
                arr[n] = list.get(n);
            }
            array4[m] = arr;
            m++;
        }
        return array4;
    }
    public static void quickSort(List<List<Integer>> aaa, Map<List<Integer>, Integer> m) {
        if(aaa.size()>0) {
            quickSort(aaa, 0 , aaa.size()-1, m);
        }
    }

    private static void quickSort(List<List<Integer>> aaa, int low, int high, Map<List<Integer>, Integer> m) {
        //1,找到遞歸算法的出口
        if( low > high) {
            return;
        }
        //2, 存
        int i = low;
        int j = high;
        //3,key
        int key = m.get(aaa.get(low));
        //4，完成一趟排序
        while( i< j) {
            //4.1 ，從右往左找到第一個小于key的數
            while(i<j && m.get(aaa.get(j)) > key){
                j--;
            }
            // 4.2 從左往右找到第一個大于key的數
            while( i<j && m.get(aaa.get(i)) <= key) {
                i++;
            }
            //4.3 交換
            if(i<j) {
                List<Integer> temp = aaa.get(i);
                aaa.set(i, aaa.get(j));
                aaa.set(j, temp);
            }
        }
        // 4.4，調整key的位置
        List<Integer> temp = aaa.get(i);
        aaa.set(i, aaa.get(low));
        aaa.set(low, temp);
        //5, 對key左邊的數快排
        quickSort(aaa, low, i-1,m);
        //6, 對key右邊的數快排
        quickSort(aaa, i+1, high,m);
    }
}
           

（官方）

無

三角形的最大周長

連結：https://leetcode-cn.com/problems/largest-perimeter-triangle

給定由一些正數（代表長度）組成的數組 A，傳回由其中三個長度組成的、面積不為零的三角形的最大周長。

如果不能形成任何面積不為零的三角形，傳回 0。

示例 1：

輸入：[2,1,2]

輸出：5

示例 2：

輸入：[1,2,1]

輸出：0

示例 3：

輸入：[3,2,3,4]

輸出：10

示例 4：

輸入：[3,6,2,3]

輸出：8

提示：

3 <= A.length <= 10000

1 <= A[i] <= 10^6

解題思路：

（我）

class Solution {
    public int largestPerimeter(int[] A) {
        int result = 0;
        sort(A);
        for (int m=A.length-1;m>1;m--){
            if (A[m-1] + A[m-2] >A[m]){
                //int p = (A[m]+A[m-1]+A[m-2])/2;
                //result = (int) Math.sqrt(p * (p-A[m]) * (p-A[m-1]) * (p-A[m-2]));
                result = A[m-1] + A[m-2] + A[m];
                break;
            }
        }
        return result;
    }

    public static void sort(int[] a){
        if(a.length>0){
            quickSort(a, 0, a.length - 1);
        }
    }
    public static void quickSort(int[] a, int low, int high){
        if (low >high){
            return;
        }
        int i=low;
        int j =high;
        int key = a[low];
        while (i<j){
            while (i<j && a[j] >key){
                j--;
            }
            while (i<j && a[i]<=key){
                i++;
            }
            if (i<j){
                int temp = a[i];
                a[i] = a[j];
                a[j] =temp;
            }
        }
        int t=a[i];
        a[i] = a[low];
        a[low]= t;
        quickSort(a, low, i-1);
        quickSort(a, i+1, high);
    }
}
           

（官方）

方法：排序

思路

不失一般性的，我們假設三角形的邊長滿足 a \leq b \leq ca≤b≤c。那麼這三條邊組成三角形的面積非零的充分必要條件是 a + b > ca+b>c。

再假設我們已經知道 cc 的長度了，我們沒有理由不從數組中選擇盡可能大的 aa 與 bb。因為當且僅當 a + b > ca+b>c 的時候，它們才能組成一個三角形。

算法

基于這種想法，一個簡單的算法就呼之欲出：排序數組。對于數組内任意的 cc，我們選擇滿足條件的最大的 a \leq b \leq ca≤b≤c，也就是大到小排序，位于 cc 後面的兩個元素。 從大到小枚舉 cc，如果能組成三角形的話，我們就傳回答案。

class Solution {
    public int largestPerimeter(int[] A) {
        Arrays.sort(A);
        for (int i = A.length - 3; i >= 0; --i)
            if (A[i] + A[i+1] > A[i+2])
                return A[i] + A[i+1] + A[i+2];
        return 0;
    }
}
           

按奇偶排序數組 II

連結：https://leetcode-cn.com/problems/sort-array-by-parity-ii

給定一個非負整數數組 A， A 中一半整數是奇數，一半整數是偶數。

對數組進行排序，以便當 A[i] 為奇數時，i 也是奇數；當 A[i] 為偶數時， i 也是偶數。

你可以傳回任何滿足上述條件的數組作為答案。

示例：

輸入：[4,2,5,7]

輸出：[4,5,2,7]

解釋：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也會被接受。

提示：

2 <= A.length <= 20000

A.length % 2 == 0

0 <= A[i] <= 1000

解題思路：

（我）

class Solution {
    public int[] sortArrayByParityII(int[] A) {
        for (int i=0;i<A.length-1;i+=2){
            if (A[i]%2!=0){
                for (int j=1;j<A.length;j+=2){
                    if (A[j]%2==0){
                        int temp = A[i];
                        A[i] = A[j];
                        A[j] = temp;
                        break;
                    }
                }
            }
        }
        return A;
    }
}
           

（官方）

方法一： 兩次周遊

思路和算法

周遊一遍數組把所有的偶數放進 ans[0]，ans[2]，ans[4]，依次類推。

再周遊一遍數組把所有的奇數依次放進 ans[1]，ans[3]，ans[5]，依次類推。

class Solution {
    public int[] sortArrayByParityII(int[] A) {
        int N = A.length;
        int[] ans = new int[N];

        int t = 0;
        for (int x: A) if (x % 2 == 0) {
            ans[t] = x;
            t += 2;
        }

        t = 1;
        for (int x: A) if (x % 2 == 1) {
            ans[t] = x;
            t += 2;
        }

        return ans;
    }
}
           

方法二： 雙指針

思路

我們可能會被面試官要求寫出一種不需要開辟額外空間的解法。

在這個問題裡面，一旦所有偶數都放在了正确的位置上，那麼所有奇數也一定都在正确的位子上。是以隻需要關注 A[0], A[2], A[4], … 都正确就可以了。

将數組分成兩個部分，分别是偶數部分 even = A[0], A[2], A[4], … 和奇數部分 odd = A[1], A[3], A[5], …。定義兩個指針 i 和 j, 每次循環都需要保證偶數部分中下标 i 之前的位置全是偶數，奇數部分中下标 j 之前的位置全是奇數。

算法

讓偶數部分下标 i 之前的所有數都是偶數。為了實作這個目标，把奇數部分作為暫存區，不斷增加指向奇數部分的指針，直到找到一個偶數，然後交換指針 i，j 所指的數。

class Solution {
    public int[] sortArrayByParityII(int[] A) {
        int j = 1;
        for (int i = 0; i < A.length; i += 2)
            if (A[i] % 2 == 1) {
                while (A[j] % 2 == 1)
                    j += 2;

                // Swap A[i] and A[j]
                int tmp = A[i];
                A[i] = A[j];
                A[j] = tmp;
            }

        return A;
    }
}
           

兩個數組的交集

連結：https://leetcode-cn.com/problems/intersection-of-two-arrays

給定兩個數組，編寫一個函數來計算它們的交集。

示例 1：

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

輸出：[2]

示例 2：

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

輸出：[9,4]

說明：

輸出結果中的每個元素一定是唯一的。

我們可以不考慮輸出結果的順序。

解題思路：

（我）

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        List<Integer> list = new ArrayList<>();
        for (int i=0;i<nums1.length;i++){
            for (int j=0;j<nums2.length;j++){
                if (nums1[i] ==nums2[j] && !list.contains(nums1[i])){
                    list.add(nums1[i]);
                }
            }
        }
        int[] array = new int[list.size()];
        for (int m=0;m<list.size();m++){
            array[m] = list.get(m);
        }
        return array;
    }
}
           

（官方）

方法一：兩個set

最直覺的方法是疊代并檢查第一個數組 nums1 中的每個值是否也存在于 nums2 中。如果存在，則将值添加到輸出。這種方法的時間複雜度為 O(n \times m)O(n×m) ，其中 n 和 m 分别為數組 nums1 和 nums2 的長度。

為了線上性時間内解決這個問題，我們使用集合 set 這一資料結構，該結構可以提供平均時間複雜度為 O(1)O(1) 的 in/contains 操作（用于測試某一進制素是否為該集合的成員）。

本解法先将兩個數組都轉換為集合，然後疊代較小的集合，檢查其中的每個元素是否同樣存在于較大的集合中。平均情況下，這種方法的時間複雜度為 O(n+m)O(n+m) 。

class Solution {
  public int[] set_intersection(HashSet<Integer> set1, HashSet<Integer> set2) {
    int [] output = new int[set1.size()];
    int idx = 0;
    for (Integer s : set1)
      if (set2.contains(s)) output[idx++] = s;

    return Arrays.copyOf(output, idx);
  }

  public int[] intersection(int[] nums1, int[] nums2) {
    HashSet<Integer> set1 = new HashSet<Integer>();
    for (Integer n : nums1) set1.add(n);
    HashSet<Integer> set2 = new HashSet<Integer>();
    for (Integer n : nums2) set2.add(n);

    if (set1.size() < set2.size()) return set_intersection(set1, set2);
    else return set_intersection(set2, set1);
  }
}
           

方法二：内置函數

如果使用内置函數：那麼平均情況下，時間複雜度為 O(n+m)O(n+m) ；而最壞的情況下，時間複雜度是 O(n \times m)O(n×m) 。

Python 提供了可用于求交集的 & 運算符，而 Java 提供了 retainAll() 函數。

class Solution {
  public int[] intersection(int[] nums1, int[] nums2) {
    HashSet<Integer> set1 = new HashSet<Integer>();
    for (Integer n : nums1) set1.add(n);
    HashSet<Integer> set2 = new HashSet<Integer>();
    for (Integer n : nums2) set2.add(n);

    set1.retainAll(set2);

    int [] output = new int[set1.size()];
    int idx = 0;
    for (int s : set1) output[idx++] = s;
    return output;
  }
}
           

兩個數組的交集 II

連結：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii

給定兩個數組，編寫一個函數來計算它們的交集。

示例 1：

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

輸出：[2,2]

示例 2:

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

輸出：[4,9]

說明：

輸出結果中每個元素出現的次數，應與元素在兩個數組中出現次數的最小值一緻。

我們可以不考慮輸出結果的順序。

進階：

如果給定的數組已經排好序呢？你将如何優化你的算法？

如果 nums1 的大小比 nums2 小很多，哪種方法更優？

如果 nums2 的元素存儲在磁盤上，記憶體是有限的，并且你不能一次加載所有的元素到記憶體中，你該怎麼辦？

解題思路：

（我）

無

（官方）

方法一：哈希表

由于同一個數字在兩個數組中都可能出現多次，是以需要用哈希表存儲每個數字出現的次數。對于一個數字，其在交集中出現的次數等于該數字在兩個數組中出現次數的最小值。

首先周遊第一個數組，并在哈希表中記錄第一個數組中的每個數字以及對應出現的次數，然後周遊第二個數組，對于第二個數組中的每個數字，如果在哈希表中存在這個數字，則将該數字添加到答案，并減少哈希表中該數字出現的次數。

為了降低空間複雜度，首先周遊較短的數組并在哈希表中記錄每個數字以及對應出現的次數，然後周遊較長的數組得到交集。

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : nums1) {
            int count = map.getOrDefault(num, 0) + 1;
            map.put(num, count);
        }
        int[] intersection = new int[nums1.length];
        int index = 0;
        for (int num : nums2) {
            int count = map.getOrDefault(num, 0);
            if (count > 0) {
                intersection[index++] = num;
                count--;
                if (count > 0) {
                    map.put(num, count);
                } else {
                    map.remove(num);
                }
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}
           

方法二：排序

如果兩個數組是有序的，則可以便捷地計算兩個數組的交集。

首先對兩個數組進行排序，然後使用兩個指針周遊兩個數組。

初始時，兩個指針分别指向兩個數組的頭部。每次比較兩個指針指向的兩個數組中的數字，如果兩個數字不相等，則将指向較小數字的指針右移一位，如果兩個數字相等，将該數字添加到答案，并将兩個指針都右移一位。當至少有一個指針超出數組範圍時，周遊結束。

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int length1 = nums1.length, length2 = nums2.length;
        int[] intersection = new int[Math.min(length1, length2)];
        int index1 = 0, index2 = 0, index = 0;
        while (index1 < length1 && index2 < length2) {
            if (nums1[index1] < nums2[index2]) {
                index1++;
            } else if (nums1[index1] > nums2[index2]) {
                index2++;
            } else {
                intersection[index] = nums1[index1];
                index1++;
                index2++;
                index++;
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}
ange(intersection, 0, index);
    }
}
           

方法二：排序

如果兩個數組是有序的，則可以便捷地計算兩個數組的交集。

首先對兩個數組進行排序，然後使用兩個指針周遊兩個數組。

初始時，兩個指針分别指向兩個數組的頭部。每次比較兩個指針指向的兩個數組中的數字，如果兩個數字不相等，則将指向較小數字的指針右移一位，如果兩個數字相等，将該數字添加到答案，并将兩個指針都右移一位。當至少有一個指針超出數組範圍時，周遊結束。

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int length1 = nums1.length, length2 = nums2.length;
        int[] intersection = new int[Math.min(length1, length2)];
        int index1 = 0, index2 = 0, index = 0;
        while (index1 < length1 && index2 < length2) {
            if (nums1[index1] < nums2[index2]) {
                index1++;
            } else if (nums1[index1] > nums2[index2]) {
                index2++;
            } else {
                intersection[index] = nums1[index1];
                index1++;
                index2++;
                index++;
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}