[问题] 袜子题的解题逻辑

楼主: 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