jotting

ⓁⒸ ‧‧‧ 350. Intersection of Two Arrays II

Posted on | Post modified | In
兩個陣列的交叉點

350. Intersection of Two Arrays II

❀ Origin

Problem

Given two arrays, write a function to compute their intersection.

Example

1
2
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2

1
2
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]

Note

  • Each element in the result should appear as many times as it shows in both arrays.
  • The result can be in any order.

Follow up

  • What if the given array is already sorted? How would you optimize your algorithm?
  • What if nums1’s size is small compared to nums2’s size? Which algorithm is better?
  • What if elements of nums2 are stored on disk,
    and the memory is limited such that you cannot load all elements into the memory at once?

❀ 翻譯

問題

給定兩個陣列，
寫出一個 function 去計算出他們的交叉點。

筆記

  • 回傳結果的每一個元素都應該出現在兩個陣列中數次以上。
  • 回傳結果可以允許任意的排序方式。

進一步思考

  • 如果給定的陣列已經排序過了怎麼辦？ 你會如何因此去優化演算法？
  • 如果 nums1 的尺寸與 nums2 的尺寸相比較小怎麼辦？ 哪種算法更好？
  • 如果 nums2 的元素都儲存在磁碟上，
    導致你無法一次將所有元素加載在內存記憶體的時候，該怎麼辦？

❀ Solution

Golang

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * 建立一個 hash 表
 **/
func intersect(nums1 []int, nums2 []int) []int {

  // 初始化一個 map ，做 hash 使用
  m := make(map[int]int)

  // 對 nums1 跑迴圈，
  // 以各個元素作為 key 值，去找 m 裡面是否有存在過，
  // 有的話加一，沒有則建立 
  for _, v := range nums1 {
    if _, ok := m[v]; ok {
      m[v]++
    } else {
      m[v] = 1
    }
  }

  // 對 nums2 跑迴圈，
  // 以各個元素作為 key 值，去找 m 裡面是否有存在，
  // 若存在，則將其值存進 ret 裡，
  // 並對 m 裡對應到的位置剪一
  // 
  // 條件判斷裡需增加 val > 0，因為 0 也會等於 ok ，
  // 不判斷的話， ret 會重複寫入。
  for _, v := range nums2 {
    if val, ok := m[v]; val > 0 && ok {
      ret = append(ret, v)
      m[v]--
    }
  }

  return ret
}

Golang

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * 先排序，之後一邊移位一邊比較，
 * 沒有建立 map ，因此記憶體的使用比較少。
 **/
func intersect(nums1 []int, nums2 []int) []int {

  // 排序陣列
  sort.Ints(nums1)
  sort.Ints(nums2)

  var i, j int
  res := []int{}

  // for 迴圈的標準條件為：nums1 或 nums2 其一結束即可
  for i < len(nums1) && j < len(nums2) {

    num1 := nums1[i]
    num2 := nums2[j]

    // 若數到 nums1 的某一數 num1 ，
    // 其值大於當前的 num2 時，
    // nums2 的陣列要往下一個前進。（ j 加一）
    if num1 > num2 {
      j++
    }

    // 若數到 nums2 的某一數 num2 ，
    // 其值大於當前的 num1 時，
    // nums1 的陣列要往下一個前進。（ i 加一）
    if num1 < num2 {
      i++
    }

    // 若 num1 、 num2 相等時，
    // 將當前數字 append 進 res ，
    // 並對 nums1 、 nums2 的陣列都往下個計算（ i 、 j 都加一）
    if num1 == num2 {
      res = append(res, num1)
      i++
      j++
    }
  }

  return res
}