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

作者: AmigoSafin   2019-06-09 11:48:24
大家好
有題屬於"簡易"的襪子題
想問問這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('#')的作用
謝謝大家了!
作者: lajji (喇機)   2019-06-09 12:25:00
這寫法實在是有點冗append('#')是因為不加的話比到最後一隻襪子會出現errorelse那邊應該是i+=1https://i.imgur.com/I9896rf.jpg 其實這樣就寫完了
作者: bibo9901 (function(){})()   2019-06-10 01:04:00
樓上的解法真是無言, 都用到set了不會用dict順便算一下?還要一遍一遍的遍歷list, 黑人問號.
作者: lemon651 (小明)   2019-06-10 01:23:00
樓上的n^2解法真是天才
作者: lajji (喇機)   2019-06-10 01:36:00
???? 五樓知道自己在說什麼嗎
作者: bibo9901 (function(){})()   2019-06-10 02:56:00
提出一個更差的做法, 再搭配"其實這樣就寫完了" 有意思
作者: benchen0812 (あBen)   2019-06-10 04:01:00
1F知道.count O(n) 嗎?
作者: adrianshum (Alien)   2019-06-11 20:26:00
我也看不明白else 那部份,i+-=1 ? 你確定沒錯嗎?比較正常的O(n) 解法大概像:(pseudo code)for n in arr:If n in a_set:count += 1remove n from a_setelse: add n to a_set
作者: sunherbcat (童話)   2019-06-14 18:16:00
else i+=1at.sort()=[1,1,1,2,2,2,3]如果a[i]==a[i+1] 則是pair , i+=2 否則 i+=1

Links booklink

Contact Us: admin [ a t ] ucptt.com