PTT數位生活區 / Python

[問題] 襪子題的解題邏輯

看板Python作者時間6年前 (2019/06/09 11:48), 編輯推噓7(7推 0噓 13→)
留言20則, 6人參與, 6年前最新討論串1/1
大家好 有題屬於"簡易"的襪子題 想問問這solution code的解題邏輯 因為是看得懂code 但不懂為何此題這樣寫(或者正確是 不太清楚這題該怎麼解) 謝謝大家~ 大感謝! John works at a clothing store. He has a large pile of socks that he must pair by color for sale. Given an array of integers representing the color of each sock, determine how many pairs of socks with matching colors there are. for example, there are n=7 socks with colors ar=[1,2,1,2,1,3,2] There is one pair of color 1 and one pair of color 2. The number of pairs is 2. Solution code: def sockMerchant(n, ar): count=0 ar.sort() ar.append('#') i=0 while i < n: if ar[i]==ar[i+1]: count=count+1 i+=2 else: i+-=1 return count 我能了解if statement上半部 如果i和i+1相同顏色 則pair count+1 但else就不太能理解 還有arr.append('#')的作用 謝謝大家了! -- -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 68.180.87.229 (美國) ※ 文章網址: https://www.ptt.cc/bbs/Python/M.1560052107.A.628.html
推
06/09 12:25, 6年前 , 1F
這寫法實在是有點冗
06/09 12:25, 1F
→
06/09 12:25, 6年前 , 2F
append('#')是因為不加的話比到最後一隻襪子會出現error
06/09 12:25, 2F
→
06/09 12:25, 6年前 , 3F
else那邊應該是i+=1
06/09 12:25, 3F
→
06/09 12:25, 6年前 , 4F
其實這樣就寫完了
06/09 12:25, 4F
→
06/10 01:04, 6年前 , 5F
樓上的解法真是無言, 都用到set了不會用dict順便算一下?
06/10 01:04, 5F
→
06/10 01:05, 6年前 , 6F
還要一遍一遍的遍歷list, 黑人問號.
06/10 01:05, 6F
推
06/10 01:23, 6年前 , 7F
樓上的n^2解法真是天才
06/10 01:23, 7F
→
06/10 01:36, 6年前 , 8F
???? 五樓知道自己在說什麼嗎
06/10 01:36, 8F
推
06/10 02:56, 6年前 , 9F
提出一個更差的做法, 再搭配"其實這樣就寫完了" 有意思
06/10 02:56, 9F
推
06/10 04:01, 6年前 , 10F
1F知道.count O(n) 嗎？
06/10 04:01, 10F
→
06/11 20:26, 6年前 , 11F
我也看不明白else 那部份，i+-=1 ? 你確定沒錯嗎？
06/11 20:26, 11F
→
06/11 20:28, 6年前 , 12F
比較正常的O(n) 解法大概像：（pseudo code)
06/11 20:28, 12F
→
06/11 20:30, 6年前 , 13F
for n in arr:
06/11 20:30, 13F
→
06/11 20:30, 6年前 , 14F
If n in a_set:
06/11 20:30, 14F
→
06/11 20:31, 6年前 , 15F
count += 1
06/11 20:31, 15F
→
06/11 20:31, 6年前 , 16F
remove n from a_set
06/11 20:31, 16F
→
06/11 20:31, 6年前 , 17F
else: add n to a_set
06/11 20:31, 17F
推
06/14 18:16, 6年前 , 18F
else i+=1
06/14 18:16, 18F
推
06/14 18:19, 6年前 , 19F
at.sort()=[1,1,1,2,2,2,3]
06/14 18:19, 19F
推
06/14 18:24, 6年前 , 20F
如果a[i]==a[i+1] 則是pair , i+=2 否則 i+=1
06/14 18:24, 20F
‣ 更多 AmigoSafin 的文章
文章代碼(AID): #1S_86BOe (Python)
Python 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 AmigoSafin 的文章
文章代碼(AID): #1S_86BOe (Python)