写在前面

博主代码小白，今年参加秋招，现在开始刷题，于是写博客整理记录一下。看完数据结构中排序的大概内容开始刷力扣题，这题是遇到的第二题，完全是刚刚开始学代码的水平，所以很多操可能相当小白，很多基础知识也不太懂。请大家多多指教。

1、题目

定义两个数组，编写一个函数来计算他们交集
示例 1：输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
示例 2:输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]
说明：
输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。我们可以不考虑输出结果的顺序。

2、思路

假定 A=[1,3,5,3,21,3,2] B=[3,2,14,5,7,6,1]

（1）先不用排序：定义一个指针指向A的第一个元素（for 循环），里面嵌套循环遍历b,相等则拷贝元素
这有一个问题：“输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。”遍历b 不加限制的话元素出现次数就会变成A*B

（2）先使用排序使得两个数组有序：
冒泡、选择、插入、归并、快速排序：对AB中的元素从小到大排序，后续取出相同元素的次数控制是不是转回了不用排序的方法比较复杂
桶排序：如果只是每个相同元素出现一次就很好用，出现次数无法控制
计数排序：先利用两个空数CD组对AB进行计数排序，选择相同的索引，对CD中各个位置的值进行比较，E储存较小值，再将E中的元素取出

（3）初定使用计数排序！
1)如何控制CD的索引值是一样的，AB长度不一范围不一：先分别取出AB的min和max，比较之后来创建新数组（max-min+1）
2）利用新数组进行AB的计数排序
3)比较CD中数值大小，并将小的数值存储在E
4）返回E数组的（索引+min）值

3、代码及调试过程的问题

3.1代码

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        int max1=nums1[0];
        int min1=nums1[0];
        int max2=nums2[0];
        int min2=nums2[0];
        max1 = getmax (max1,nums1);
        min1 = getmin(min1,nums1);
        max2 = getmax (max2,nums2);
        min2 = getmin(min2,nums2);
        int min = min1<min2?min1:min2;
        int max = max1>max2?max1:max2;
        int[] L1 = new int[max-min+1];
        int[] L2 = new int[max-min+1];
        for (int i=0;i<nums1.length;i++){#遍历数组里的元素还可以 for(int num : nums1)
            L1[nums1[i]-min]++;
        }
        for (int i=0;i<nums2.length;i++){
            L2[nums2[i]-min]++;
        }
        int[] L = new int[max-min+1];
        for (int i=0;i<L.length;i++){
            L[i]=L1[i]<L2[i]?L1[i]:L2[i];
        }
        ArrayList<Integer> res = new ArrayList<>();
        int index=0;
        for(int i=0;i<L.length;i++){
            while(L[i]>0){
                res.add(i+min);
                L[i]--;
            }
        }
        int size= res.size();
        // Integer[] res1 =res.toArray(new Integer [size]);
        int[] res1 = res.stream().mapToInt(Integer::valueOf).toArray();
        return res1;

    }
    public int getmax(int max ,int[] num){
        for(int i=0;i<num.length;i++){
           
            if(num[i]>max){
                max=num[i];
            }
        }
        return (max);
    }
    public int getmin( int min,int[] num){
        for(int i=0;i<num.length;i++){
            if(num[i]<min){
                min=num[i];
            }
        }
        return (min);
    }
}




复制代码

3.2 调试出现的问题

（1）index超出界限

在这里插入图片描述
分析：15行的限制条件应该是读取nums1中的元素，所以应该是i<nums1.length而不是L.length
补充：length是string的属性，length（）是数组的方法，size（）是List的方法

（2）index超出范围

在这里插入图片描述
分析：Index++最后到9？取出来过的L数值没有-1，导致L一直是>0，一直循环，导致count值超标。L[i]--

(3) 返回的数组出现00

在这里插入图片描述
分析：int定义数组的时候一开始就分配好了空间，没有值的返回0 ，有两种解决办法：
1）使用ArrayList来动态控制数组大小

 ArrayList<Integer> res = new ArrayList<>();
        int index=0;
        for(int i=0;i<L.length;i++){
            while(L[i]>0){
                res.add(i+min);
                L[i]--;
            }
        }
复制代码

但是使用ArrayList直接return res会因为类型报错，必须先转换成int类型：int[] res1 = res.stream().mapToInt(Integer::valueOf).toArray();或者

 int[] res1 = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            res[i] = res.get(i);
        }
复制代码

2)直接拷贝数组的前半有值的部分

return Arrays.copyOfRange(res,0,index)
复制代码

可以视情况而定使用其中某种方法，当然欢迎补充，楼主刚刚接触代码，这里的所有认识都来自于后面整理的力扣的官方解答和本题评论区。
在这里插入图片描述
运行成功！！！自己写出来的第一题，骄傲！！（昨天刷第一题的时候完全不知道怎么下手，看了一遍官方解答再写的）虽然时间复杂度很高….但是慢慢来，菜鸟成长史。运行成功那刻真的超开心哈哈

4、官方解答理解

官方方法是利用哈希表，由于哈希表的数据结构还没有看概念，简单查了一下，设置关键字key，将key的函数直接作为地址储存数据，是一种映射。
这题里面就是把先遍历数组nums1,里面的值直接作为key，然后映射值来储存次数(那是不是有点像桶,类似桶的二维数组？)之后再遍历nums2相同元素就取出作为答案，同时count–,后再将key和count放入map,count为0时移除元素。贴一下理解

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
       if (nums1.length > nums2.length) {
            return intersect(nums2, nums1);#intersect函数为取两个数组的交集，这里没太看懂，直接返回交集吗
            #那相同元素出现的次数是1吗。“其在交集中出现的次数等于该数字在两个数组中出现次数的最小值。 ”
            #那这样不是一步到位了吗。查了下发现java没有这个函数，
            #猛然发现这是一个本身的调用这一步是为了遍历较短的数组！！！！好妙啊
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();#创建一个哈希表，有点类似二维数组，一个放key值，一个放出现次数
        for (int num : nums1) {#用一个标志num来遍历nums1
            int count = map.getOrDefault(num, 0) + 1;#getOrDefault的用法：如果map中存在num,就使用它的值
            #没有就用0，就是统计num出现的次数。get就是返回num所映射的值
            map.put(num, count);#将num 和count 放入map，在这打了个断点，结果见右边
        }
        int[] intersection = new int[nums1.length];#新建数组用来存储结果
        int index = 0;#index来控制结果数组的元素存储
        for (int num : nums2) {
            int count = map.getOrDefault(num, 0);#有相同的元素则读取map中的值，即出现的次数
            if (count > 0) {
                intersection[index++] = num;#有相同元素，输出
                count--;#count--
                if (count > 0) {
                #不止出现一次，再将自减后的num和count放入map
                    map.put(num, count);
                } else {
                    map.remove(num);
                }
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);#复制数组0<=i<index中的元素，这样就可以避免int一开始开辟固定空间之后出现的0值
    }
}

复制代码

5、优化

如果数组已经拍好序了，如何优化算法

思路：
排好序有什么便利呢?方便统计出现的次数，从左到右就可。用双指针
1）i指向s1第一个元素，j指向s2第一个元素
2）同时右移，如果s1[i]=s2[j]，记录元素（这样会出现问题，需要一个大小的比较）
应该是，相等则记录并同时右移，不等的话右移小的。s1[i]<s2[j]?右移s1[i]:右移s2[i]
3）一个指针超范围就停止
思路比较明确，但怎么转换成代码有点疑惑，这里先看了眼官方解答。

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        int i = 0;
        int j = 0;
        int L1 = nums1.length;
        int L2 = nums2.length;
        ArrayList<Integer> res=new ArrayList<>();
        while (i<L1&&j<L2){
            if (nums1[i]==nums2[j]){
                res.add(nums1[i]);
                i++;
                j++;
            }
            if (nums1[i]<nums2[j]){
            #这里运行发现报一个 index out of bound的错误，应该改为else if 
                i++;
            }
            if (nums1[i]>nums2[j]){
                j++;
            }
        } 
        int[] res1=res.stream().mapToInt(Integer::valueOf).toArray();
        return res1;

    }
}

复制代码

报错：
在这里插入图片描述
分析：在多个if语句中,所有的if都会进行判断，所以index会超过界限。
多个if条件时，需要使用elseif 表示if不成立时再次进行条件判断，进行一次判断，成功了！

官方代码：

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);#sort函数：对数组进行排序
        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);
    }
}

复制代码