Python Counting Related Questions

Links to the original text:

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)]
  • 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.
  • 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})
'''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[0])
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: [1]

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[0] 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:
'e'appeared twice, and'r' and't'appeared only once.
So'e'must appear before'r' and't'. In addition, "eetr" is an effective answer.
Example 2:
'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:
In addition, "bbaA" is an effective answer, but "Aabb" is incorrect.
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][0]       #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

Keywords: Lambda Python

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