Question

1213. 三个有序数组的交集

English Version

题目描述

给出三个均为 严格递增排列 的整数数组 arr1，arr2 和 arr3。返回一个由 仅 在这三个数组中 同时出现 的整数所构成的有序数组。

 

示例 1：

输入: arr1 = [1,2,3,4,5], arr2 = [1,2,5,7,9], arr3 = [1,3,4,5,8]
输出: [1,5]
解释: 只有 1 和 5 同时在这三个数组中出现.

示例 2:

输入: arr1 = [197,418,523,876,1356], arr2 = [501,880,1593,1710,1870], arr3 = [521,682,1337,1395,1764]
输出: []

 

提示：

• 1 <= arr1.length, arr2.length, arr3.length <= 1000
• 1 <= arr1[i], arr2[i], arr3[i] <= 2000

解法

方法一：计数

遍历三个数组，统计每个数字出现的次数，然后遍历任意一个数组，若某个数字出现的次数为 $3$，则将其加入结果数组。

时间复杂度 $O(n)$，空间复杂度 $O(m)$。其中 $n$ 和 $m$ 分别为数组的长度和数组中数字的范围。

class Solution:
  def arraysIntersection(
    self, arr1: List[int], arr2: List[int], arr3: List[int]
  ) -> List[int]:
    cnt = Counter(arr1 + arr2 + arr3)
    return [x for x in arr1 if cnt[x] == 3]

class Solution {
  public List<Integer> arraysIntersection(int[] arr1, int[] arr2, int[] arr3) {
    List<Integer> ans = new ArrayList<>();
    int[] cnt = new int[2001];
    for (int x : arr1) {
      ++cnt[x];
    }
    for (int x : arr2) {
      ++cnt[x];
    }
    for (int x : arr3) {
      if (++cnt[x] == 3) {
        ans.add(x);
      }
    }
    return ans;
  }
}

class Solution {
public:
  vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
    vector<int> ans;
    int cnt[2001]{};
    for (int x : arr1) {
      ++cnt[x];
    }
    for (int x : arr2) {
      ++cnt[x];
    }
    for (int x : arr3) {
      if (++cnt[x] == 3) {
        ans.push_back(x);
      }
    }
    return ans;
  }
};

func arraysIntersection(arr1 []int, arr2 []int, arr3 []int) (ans []int) {
  cnt := [2001]int{}
  for _, x := range arr1 {
    cnt[x]++
  }
  for _, x := range arr2 {
    cnt[x]++
  }
  for _, x := range arr3 {
    cnt[x]++
    if cnt[x] == 3 {
      ans = append(ans, x)
    }
  }
  return
}

class Solution {
  /**
   * @param Integer[] $arr1
   * @param Integer[] $arr2
   * @param Integer[] $arr3
   * @return Integer[]
   */
  function arraysIntersection($arr1, $arr2, $arr3) {
    $rs = [];
    $arr = array_merge($arr1, $arr2, $arr3);
    for ($i = 0; $i < count($arr); $i++) {
      $hashtable[$arr[$i]] += 1;
      if ($hashtable[$arr[$i]] === 3) {
        array_push($rs, $arr[$i]);
      }
    }
    return $rs;
  }
}

方法二：二分查找

遍历第一个数组，对于其中的每个数字，使用二分查找在第二个数组和第三个数组中查找该数字，若都找到，则将该数字加入结果数组。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(1)$。其中 $n$ 为数组的长度。

class Solution:
  def arraysIntersection(
    self, arr1: List[int], arr2: List[int], arr3: List[int]
  ) -> List[int]:
    ans = []
    for x in arr1:
      i = bisect_left(arr2, x)
      j = bisect_left(arr3, x)
      if i < len(arr2) and j < len(arr3) and arr2[i] == x and arr3[j] == x:
        ans.append(x)
    return ans

class Solution {
  public List<Integer> arraysIntersection(int[] arr1, int[] arr2, int[] arr3) {
    List<Integer> ans = new ArrayList<>();
    for (int x : arr1) {
      int i = Arrays.binarySearch(arr2, x);
      int j = Arrays.binarySearch(arr3, x);
      if (i >= 0 && j >= 0) {
        ans.add(x);
      }
    }
    return ans;
  }
}

class Solution {
public:
  vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
    vector<int> ans;
    for (int x : arr1) {
      auto i = lower_bound(arr2.begin(), arr2.end(), x);
      auto j = lower_bound(arr3.begin(), arr3.end(), x);
      if (*i == x && *j == x) {
        ans.push_back(x);
      }
    }
    return ans;
  }
};

func arraysIntersection(arr1 []int, arr2 []int, arr3 []int) (ans []int) {
  for _, x := range arr1 {
    i := sort.SearchInts(arr2, x)
    j := sort.SearchInts(arr3, x)
    if i < len(arr2) && j < len(arr3) && arr2[i] == x && arr3[j] == x {
      ans = append(ans, x)
    }
  }
  return
}