# d478 - 共同的數 (簡易版)

### 題目連結: [d478](https://zerojudge.tw/ShowProblem?problemid=d478)

### 題目解析
* 在兩串數列當中，尋找相同的數字，並記錄有幾個重複

### 題目類型
流程控制/複雜度/程式優化

### 範例測資解讀
* 輸入
* 不固定的多組資料，第一行兩個數字 n, m，分別代表有n筆測資，每行測資有m個數字
* 接下來的測資每兩行為一組，數字皆為m個
* 輸出
* 輸出兩行數字當中共同的數一共有幾個

### 其他注意事項
* 此題是簡化版的數列搜尋，簡化的項目包含：
* 單行數列中的數字不會重複
* 由小到大依序排列

### 程式解析
此題的程式邏輯很簡單，以一行數列為基準，去檢查另外一行的數列，是否有相同的數字

for j in seq1:
    if j in seq2: # in seq2 其實是所有的數字都檢查判斷一次
        sum +=1

但這樣的邏輯使用迴圈實現是會有問題的，檢查相同數字的時候，可能會有過多無意義的判斷
例如以下這組數列：
* 10 12 14 16 18
* 20 22 24 26 28

可以發現無論如何搜尋，都無法找到共同的數字，像這種情況如果程式一樣執行迴圈，則全部的判斷都是無效的

若測試的數列較長，則會發現造成程式執行效率下降

### 完整版程式碼 (NA50, 簡易版, 但無法全對)

# start
Line1 = input().split()

N = int(Line1[0])
M = int(Line1[1])

for i in range(N):

    sum = 0

    data = input()
    seq1 = list(map(int, data.split()))

    data2 = input()
    seq2 = list(map(int, data2.split()))
  
    for j in seq1:
        if j in seq2:
            sum +=1
            
    print(sum)


在 d478 這題由測資資訊可以發現，第二組測資的內容相當龐大，純文字檔的檔案大小竟然接近 50MB

如果使用原本的方法搜尋，則會出現 TLE 的訊息，代表程式執行效率太差，需要改良優化

在此題我們優化的方式是使用 sort()
想法是這樣的：
* 10 11 15 18 19
* 9 12 15 16 19

將 seq1, seq2 兩組數列合併成為一個兩倍大小的數列，並進行 sort() 排序
排序的目的是要找出兩兩成對的數字，最後在使用單一迴圈檢查數列有幾組兩兩成對的數字，即為重複的數字
因此上述的數列會變成
* 9 10 11 12 <font color=red>15 15</font> 16 18 <font color=red>19 19</font>

如此就可以簡化迴圈搜尋的次數，達到程式執行效能優化

### 完整版程式碼2 (AC)

import sys

# start
Line1 = input().split()

N = int(Line1[0])
M = int(Line1[1])

for i in range(N):

    sum = 0

    data1 = input()
    data2 = input()

    data = data1+" "+data2
    seq = list(map(int, data.split()))
    
    seq.sort()
    
    for x in range(len(seq)-1):
        if seq[x] == seq[x+1]:
            sum +=1

    print(sum)

以上為一種優化程式碼的方式，除了這種方法外，亦有其他種解法

###### tags: `基礎15題解` `APCS` `ZeroJudge`