算法练习100天-第3天

类别：数组

题目： 349. 两个数组的交集

我的解题思路：

class Solution {
    /**
    1.要求返回一个整型，元素不重复数组，可以利用集合set的特性
    2.先将一个nums1值保存在set1中，循环nums2，判断set1中是否存在nums2中的值，存在则保存在set2中
    3.将set2转换为int[]
      >先将set2转为Integer型数组
      >再将Integer型数组转为int型数组
    **/
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet();
        Set<Integer> set2 = new HashSet();
        for (int a : nums1) {
            set1.add(a);
        }
        for (int b : nums2) {
            if (set1.contains(b)) {
                set2.add(b);
            }
        }
        Integer[] temp = set2.toArray(new Integer[] {});
        int[] intArray = new int[temp.length];
        for (int i = 0; i < temp.length; i++) {
            intArray[i] = temp[i].intValue();
        }
        return intArray;
    }
}

官方解题思路：

方法1：Set（题解中出现最多的）

 public int[] intersection(int[] nums1, int[] nums2) {
    if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
      return new int[0];
    }
    Set<Integer> parentSet = new HashSet<>();
    Set<Integer> childSet = new HashSet<>();
    for (int num : nums1) {
      parentSet.add(num);
    }
    for (int num : nums2) {
      if (parentSet.contains(num)) {
        childSet.add(num);
      }
    }
    int[] resArr = new int[childSet.size()];
    int index = 0;
    for (int value : childSet) {
      resArr[index++] = value;
    }
    return resArr;
  }

方法2：双指针
先将nums1 与nums2排序，然后游走两个指针，情况都写出来了，没有用else
时间复杂度：O(nlogn)

public int[] intersection(int[] nums1, int[] nums2) {
  Set<Integer> set = new HashSet<>();
  Arrays.sort(nums1);
  Arrays.sort(nums2);
  int i = 0, j = 0;
  while (i < nums1.length && j < nums2.length) {
    if (nums1[i] == nums2[j]) {
      set.add(nums1[i]);
      i++;
      j++;
    } else if (nums1[i] < nums2[j]) {
      i++;
    } else if (nums1[i] > nums2[j]) {
      j++;
    }
  }
  int[] res = new int[set.size()];
  int index = 0;
  for (int num : set) {
    res[index++] = num;
  }
  return res;
}

方法3：二分查找
将nums2排序，然后查找nums2的元素，需要准备一个binarySearch的辅助方法，注意left<= right

public int[] intersection(int[] nums1, int[] nums2) {
  Set<Integer> set = new HashSet<>();
  Arrays.sort(nums2);
  for (int target : nums1) {
    if (binarySearch(nums2, target) && !set.contains(target)) {
      set.add(target);
    }
  }
  int index = 0;
  int[] res = new int[set.size()];
  for (int num : set) {
    res[index++] = num;
  }
  return res;
}
public boolean binarySearch(int[] nums, int target) {
  int left = 0, right = nums.length - 1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) {
      return true;
    } else if (nums[mid] > target) {
      right = mid - 1;
    } else if (nums[mid] < target) {
      left = mid + 1;
    }
  }
  return false;
}

差异点

• 没有想到将数组排序，排序后的数组可以用二分查找法来判断两个数组中是否存在相同值