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

[AmigoSafin ()]

大家好

有題屬於"簡易"的襪子題

想問問這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
推 lajji: 這寫法實在是有點冗
→ lajji: append('#')是因為不加的話比到最後一隻襪子會出現error
→ lajji: else那邊應該是i+=1
→ lajji: https://i.imgur.com/I9896rf.jpg 其實這樣就寫完了
→ bibo9901: 樓上的解法真是無言, 都用到set了不會用dict順便算一下?
→ bibo9901: 還要一遍一遍的遍歷list, 黑人問號.
推 lemon651: 樓上的n^2解法真是天才
→ lajji: ???? 五樓知道自己在說什麼嗎
推 bibo9901: 提出一個更差的做法, 再搭配"其實這樣就寫完了" 有意思
推 benchen0812: 1F知道.count O(n) 嗎？
→ adrianshum:  我也看不明白else 那部份，i+-=1 ? 你確定沒錯嗎？
→ adrianshum: 比較正常的O(n) 解法大概像：（pseudo code)
→ adrianshum: for n in arr:
→ adrianshum:   If n in a_set:
→ adrianshum:     count += 1
→ adrianshum:     remove n from a_set
→ adrianshum:   else: add n to a_set
推 sunherbcat: else i+=1
推 sunherbcat: at.sort()=[1,1,1,2,2,2,3]
推 sunherbcat: 如果a[i]==a[i+1] 則是pair , i+=2 否則 i+=1