# Python Counting Related Questions

Links to the original text: https://www.jianshu.com/p/24dd4e194a97

# python Counting Related Questions

In the brief book, I saw an article introducing the "counting" related questions on Leetcode, and introduced some very clever methods, so I reprinted it for record.

Question: Given a sequence, count the number of occurrences of all elements

• Method 1: seq.count()
```seq = 'abcdbabaecccdbb'  #To-be-counted sequence
#Change into a collection to get all the elements in seq, avoiding repetitive traversal
set_seq = set(seq)
rst = []
for item in set_seq:
rst.append((item,seq.count(item)))  #Adding elements and number of occurrences
#Output result, [('a', 3), ('e', 1), ('b', 5), ('c', 4), ('d', 2)]
print(rst)
```
• Law 2: Use dictionary dict
```seq='abcdbabaecccdbb'  #To-be-counted sequence
dict = {}
for item in seq:       #Traversal str
if item not in dict:  #For the first time, assign an initial value of 1
dict[item] = 1
else:                 #Number of occurrences plus one
dict[item] += 1
#The results {a': 3,'b': 5,'c': 4,'d': 2,'e': 1} are obtained.
print(dict)
```
• Method 3: Use Counter class in built-in module collections
```'''Counter Is used to compute hash objects dict Subclass,
//Where elements are stored in dictionary keys and counts are stored in dictionary values
//Not Hash: Lists, Collections, Dictionaries
//Hash: Number, tuple, string, Boolean type'''

from collections import Counter

seq ='abcdbabaecccdbb'  #To-be-counted sequence
'''Counter()Statistical number of occurrences of each element'''
counter = Counter(seq)
#counter --> Counter({'b': 5, 'c': 4, 'a': 3, 'd': 2, 'e': 1})
print(counter)

'''most_common(n)Before the occurrence of Statistics n Bit element'''
most = counter.most_common()
#most --> [('b', 5), ('c', 4), ('a', 3), ('d', 2), ('e', 1)]

'''You can specify the number of outputs and the sort method'''
most_one = counter.most_common(1)
print(most_one)  #most_one --> [('b', 5)]
#Sort by element size in ascending order
most.sort(key = lambda item:item)
print(most)  #most --> [('a', 3), ('b', 5), ('c', 4), ('d', 2), ('e', 1)]
#Sort in descending order according to the number of occurrences
most.sort(key = lambda item:item[-1],reverse = True)
print(most)  #most --> [('b', 5), ('c', 4), ('a', 3), ('d', 2), ('e', 1)]
```

## LeetCode 347: The first k high-frequency elements

Title Description: Given a non-empty integer array, return the element with the highest k before its occurrence frequency.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = 1], k = 1
Output: 

```from collections import Counter
class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
cnt = Counter(nums)
top_k = cnt.most_common(k)        #Return the first k high-frequency elements in nums
return [rst for rst in top_k]  #Return results

result = Solution()
nums = [1,2,3,2,3,4,3,1,2,4,4,5,4,2,2]
#Take a look at nums statistics first
print(Counter(nums)) # Counter({2: 5, 4: 4, 3: 3, 1: 2, 5: 1})
#The first k high frequency elements
print(result.topKFrequent(nums,3))  #[2, 4, 3]
```

## LeetCode 451: Sort by character occurrence frequency

Title Description: Given a string, please arrange the characters in the string in descending order according to the frequency of occurrence.
Example 1:
Input:
"tree"
Output:
"eert"
Explanation:
'e'appeared twice, and'r' and't'appeared only once.
Example 2:
Input:
"cccaaa"
Output:
"cccaaa"
Explanation:
'c'and'a' appeared three times. In addition, "aaaccc" is also an effective answer.
Note that "cacaca" is incorrect because the same letters must be put together.
Example 3:
Input:
"Aabb"
Output:
"bbAa"
Explanation:
Note that'A'and'a' are considered to be two different characters.

```from collections import Counter
class Solution(object):
def frequencySort(self, s):
"""
:type s: str
:rtype: str
"""
rst = ''
cnt = Counter(s)
most = cnt.most_common()
#Arrange the characters in the string in descending order according to the frequency of occurrence
most.sort(key = lambda x: x[-1],reverse = True)
for element,count in most:   #ergodic
rst += element * count   #Element - > Element
return rst                   #Count - > Number of occurrences

result = Solution()
print(result.frequencySort("tree"))  #eetr
print(result.frequencySort("bbAa"))  #bbAa
```

### LeetCode 136: Numbers that appear only once

Title Description: Given a non-empty integer array, each element occurs twice except for one element. Find the element that appears only once.
Example 1:
Input: [2,2,1]
Output: 1
Example 2:
Input: [4, 1, 2, 1, 2]
Output: 4

```from collections import Counter
class Solution:
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
cnt = Counter(nums)
s = cnt.most_common(len(nums))  #Return (value, number) and sort by number of occurrences
return s[-1]       #The element that appears once is at the end

'''    Method 2:
^ XOR-->Self-difference or gain 0, 1^1 --> 0. Be different from 0 or get oneself,  123^0 --> 123
//XOR satisfies the exchange law - > 1 ^ 2 ^ 1 = 1 ^ 1 ^ 2 - > 2.
2^3^4^2^3 == 2^2^3^3^4 --> 4
//Because there is only one element that appears once, the result can be obtained by XOR for all elements in nums.
rst = 0
for num in nums:
rst ^= num
return rst
'''

result = Solution()
print(result.singleNumber([4,1,2,1,2]))   #4
```

For leetcode 136, I think the author's "XOR" method is better and worth learning.

Reproduced from:
Python counter | collections.Counter
https://www.jianshu.com/p/24dd4e194a97

Keywords: Lambda Python

Added by zc1 on Thu, 08 Aug 2019 12:48:49 +0300