排序----349. 两个数组的交集I &&350. 两个数组的交集II

ゞ浴缸里的玫瑰 2022-11-16 10:48 197阅读 0赞

349  
【题目】  
给定两个数组，编写一个函数来计算它们的交集。

【示例】  
输入：nums1 = \[1,2,2,1\], nums2 = \[2,2\]  
输出：\[2\]

350  
【题目】  
给定两个数组，编写一个函数来计算它们的交集。

【示例】  
输入：nums1 = \[1,2,2,1\], nums2 = \[2,2\]  
输出：\[2,2\]

【思路】  
排序+双指针  
两题区别：结果的唯一性  
【代码】

class Solution { 
        public int[] intersection(int[] nums1, int[] nums2) { 
            Arrays.sort(nums1);
            Arrays.sort(nums2);
            int length1 = nums1.length, length2 = nums2.length;
            int[] intersection = new int[length1 + length2];
            int index = 0, index1 = 0, index2 = 0;
            while (index1 < length1 && index2 < length2) { 
                int num1 = nums1[index1], num2 = nums2[index2];
                if (num1 == num2) { 
                    // 保证加入元素的唯一性
                    if (index == 0 || num1 != intersection[index - 1]) { 
                        intersection[index++] = num1;
                    }
                    index1++;
                    index2++;
                } else if (num1 < num2) { 
                    index1++;
                } else { 
                    index2++;
                }
            }
            return Arrays.copyOfRange(intersection, 0, index);
        }
    }
    
    作者：LeetCode-Solution
    链接：https://leetcode-cn.com/problems/intersection-of-two-arrays/solution/liang-ge-shu-zu-de-jiao-ji-by-leetcode-solution/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

350

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