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);
    }
}