两个数组的交集[数组]
2018-10-07 本文已影响0人
正经龙
链接：java中CopyOf的用法
题目描述
题目
实现思路
- 两个数组排序
- 判断两个数组谁比较小
- 在较大的数组中遍历一遍，寻找较小的数组中的数
- 找到相等的就保存起来，下标向后移动一位，下次遍历从本次的后一位开始。
代码版本(一) 通过率仅击败了14%
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int array1_size = nums1.length;
int array2_size = nums2.length;
boolean first_big = (array1_size>array2_size);
ArrayList<Integer> list = new ArrayList<Integer>();
if(first_big){
int remember = 0;
for(int i = 0;i < array2_size;i++){
for(int j=remember;j<array1_size;j++){
if(nums1[j] == nums2[i]){
list.add(nums1[j]);
remember = j+1;
break;
}
}
}
}
else{
int remember = 0;
for(int i = 0;i < array1_size;i++){
for(int j=remember;j<array2_size;j++){
if(nums2[j] == nums1[i]){
list.add(nums2[j]);
remember = j+1;
break;
}
}
}
}
int []reArray = new int[list.size()];
for(int i = 0;i<list.size();i++){
reArray[i] = list.get(i);
}
return reArray;
}
}
通过情况
通过情况
改进思路
- 数组排序
- 设置两个遍历指针
- 创建一个数组用于保存交集
- 如果两个数相等，遍历指针都向后移一位
- 如果不想等，数值较小的那个数组遍历指针向后移动一位
- 当有一个数组越界时停止判断
- 复制当前返回数组的前K个，k为相等的数的个数
代码版本（二）
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int len1 = nums1.length;
int len2 = nums2.length;
int[] save = new int[len1 > len2 ? len1:len2];
int i=0,j=0,k=0;
while (i<len1 && j<len2){
if(nums1[i]==nums2[j]) {
save[k]=nums1[i];
i++;j++;k++;
}else if(nums1[i]<nums2[j]) {
i++;
}else {
j++;
}
}
return Arrays.copyOf(save, k);
}
}
通过情况
通过
