Viết chương trình tìm phần tử chiếm đa số trong mảng bằng Python

Đề bài: Tìm phần tử chiếm đa số trong một mảng. Một phần tử chiếm đa số trong mảng A[] với kích thước mảng là n là phần tử xuất hiện hơn n/2 lần.

Ví dụ:

Input : {3, 3, 4, 2, 4, 4, 2, 4, 4}
Output : 4
Giải thích: Tần suất xuất hiện của 4 là 5 lớn hơn một nửa kích thước của mảng. 

Input : {3, 3, 4, 2, 4, 4, 2, 4}
Output : Không có phần tử chiếm đa số
Giải thích: Không có phần tử nào có tần suất xuất hiện lớn hơn một nửa kích thước của mảng.

Trong bài viết này, Quản Trị Mạng sẽ cùng các bạn tìm hiểu cách viết chương trình xác định phần tử chiếm đa số bằng ngôn ngữ lập trình Python.

Cách 1: Cách xử lý đơn giản nhất

Giải pháp cơ bản nhất là dùng hai vòng lặp để đếm số lần xuất hiện tối đa của tất cả các phần tử khác nhau. Nếu số lần xuất hiện tối đa lớn hơn n/2, dừng vòng lặp và trả về phần tử có số lần xuất hiện tốn đa. Nếu số lần xuất hiện tối đa không lớn hơn n/2 thì phần tử chiếm đa số không tồn tại.

Minh họa cho giải pháp:

arr[] = {3, 4, 3, 2, 4, 4, 4, 4}, n = 8

For i = 0:

count = 0
- Lặp qua toàn bộ mảng, khi một phần tử bằng với arr[i] (là 3), tăng count
- count của arr[i] là 2, số này nhỏ hơn n/2, do vậy nó không phải là phần tử chiếm đa số

For i = 1:

count = 0
- Lặp qua toàn bộ mảng, khi một phần tử bằng với arr[i] (là 4), tăng count
- count của arr[i] là 5, số này lớn hơn n/2 (là 4), do vậy nó chính là phần tử chiếm đa số

Kết luận, 4 là phần tử chiếm đa số.

Làm theo các bước dưới đây để giải quyết vấn đề:

• Tạo một biến để lưu trữ count tối đa, count = 0.
• Duyệt qua bảng từ đầu tới cuối.
• Với một phần tử ở trong mảng, chạy một vòng lặp khác để tìm tần suất xuất hiện của các phần tử tương tự trong mảng đã cho.
• Nếu tần suất xuất hiện (count) lớn hơn tần suất xuất hiện tối đa, cập nhật tần suất xuất hiện tối đa (count tối đa) và lưu trữ chỉ số trong một biến khác.
• Nếu tần suất xuất hiện tối đa lớn hơn so với một nửa kích thước của mảng, in ra phần tử. Nếu không, trả về thông báo rằng mảng không có phần tử chiếm đa số.

Dưới đây là code mẫu để các bạn tham khảo:

# Python3 program to find Majority
# element in an array
 
# Function to find Majority
# element in an array
 
 
def findMajority(arr, n):
 
    maxCount = 0
    index = -1  # sentinels
    for i in range(n):
 
        count = 0
        for j in range(n):
 
            if(arr[i] == arr[j]):
                count += 1
 
        # update maxCount if count of
        # current element is greater
        if(count > maxCount):
 
            maxCount = count
            index = i
 
    # if maxCount is greater than n/2
    # return the corresponding element
    if (maxCount > n//2):
        print(arr[index])
 
    else:
        print("No Majority Element")
 
 
# Driver code
if __name__ == "__main__":
    arr = [1, 1, 2, 1, 3, 5, 1]
    n = len(arr)
 
    # Function calling
    findMajority(arr, n)
 
# This code is contributed
# by ChitraNayal

Cách 2: Sử dụng cây tìm kiếm nhị phân (BST)

Thêm từng phần tử vào BTS và nếu phần tử đó đã hiện diện, tăng số lượt đếm của nút. Ở bất kỳ giai đoạn nào, nếu số lượt đếm của một nút lớn hơn n/2 thì in ra phần tử.

Làm theo các bước dưới đây để giải quyết vấn đề:

• Tạo một cây tìm kiếm nhị phân, nếu cùng một phần tử được nhập vào cây tìm kiếm nhịn phân, tần suất của nút sẽ được tăng lên.
• Duyệt qua mảng và thêm phần tử vào cây tìm kiếm nhị phân.
• Nếu giá trị tần suất tối đa của bất kỳ nút nào lớn hơn một nửa kích thước của mảng, thực hiện truyền tải theo thứ tự và tìm nút đó.
• Nếu không, trả về thông báo mảng không có phần tử chiếm đa số.

Dưới đây là code mẫu để các bạn tham khảo:

# Python3 program to demonstrate insert operation in binary
# search tree.
# class for creating node
class Node():
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.count = 1  # count of number of times data is inserted in tree
 
# class for binary search tree
# it initialises tree with None root
# insert function inserts node as per BST rule
# and also checks for majority element
# if no majority element is found yet, it returns None
 
 
class BST():
    def __init__(self):
        self.root = None
 
    def insert(self, data, n):
        out = None
        if (self.root == None):
            self.root = Node(data)
        else:
            out = self.insertNode(self.root, data, n)
        return out
 
    def insertNode(self, currentNode, data, n):
        if (currentNode.data == data):
            currentNode.count += 1
            if (currentNode.count > n//2):
                return currentNode.data
            else:
                return None
        elif (currentNode.data < data):
            if (currentNode.right):
                self.insertNode(currentNode.right, data, n)
            else:
                currentNode.right = Node(data)
        elif (currentNode.data > data):
            if (currentNode.left):
                self.insertNode(currentNode.left, data, n)
            else:
                currentNode.left = Node(data)
 
 
# Driver code
# declaring an array
arr = [3, 2, 3]
n = len(arr)
 
# declaring None tree
tree = BST()
flag = 0
for i in range(n):
    out = tree.insert(arr[i], n)
    if (out != None):
        print(arr[i])
        flag = 1
        break
if (flag == 0):
    print("No Majority Element")

Cách 3: Sử dụng thuật toán Voting của Moore

Đây là một quá trình gồm 2 bước:

• Bước thứ nhất đưa ra phần tử có thể là phần tử chiếm đa số trong mảng. Nếu có một phần tử chiếm đa số trong mảng thì bước này chắc chắn sẽ trả về phần tử chiếm đa số đó. Nếu không, nó sẽ trả về ứng cử viên cho phần tử chiếm đa số.
• Bước thứ hai là kiểm tra phần tử chiếm đa số thu được từ bước trên có thực sự là phần tử chiếm đa số hay không. Bước này là cần thiết phải có bởi tồn tại trường hợp không có phần tử chiếm đa số.

Minh họa cho giải pháp:

arr[] = {3, 4, 3, 2, 4, 4, 4, 4}, n = 8

maj_index = 0, count = 1

Ở i = 1: arr[maj_index] != arr[i]

- count = count – 1 = 1 – 1 = 0
- now count == 0 then:
    - maj_index = i = 1
    - count = count + 1 = 0 + 1 = 1

Ở i = 2: arr[maj_index] != arr[i]

- count = count – 1 = 1 – 1 = 0
- now count == 0 then:
    - maj_index = i = 2
    - count = count + 1 = 0 + 1 = 1

Ở i = 3: arr[maj_index] != arr[i]

- count = count – 1 = 1 – 1 = 0
- now count == 0 then:
    - maj_index = i = 3
    - count = count + 1 = 0 + 1 = 1

Ở i = 4: arr[maj_index] != arr[i]

- count = count – 1 = 1 – 1 = 0
- now count == 0 then:
    - maj_index = i = 4
    - count = count + 1 = 0 + 1 = 1

Ở i = 5: arr[maj_index] == arr[i]

- count = count + 1 = 1 + 1 = 2

Ở i = 6: arr[maj_index] == arr[i]

- count = count + 1 = 2 + 1 = 3

Ở i = 7: arr[maj_index] == arr[i]

- count = count + 1 = 3 + 1 = 4

Do đó, arr[maj_index] có khả năng là ứng viên phần tử chiếm đa số.

Bây giờ, duyệt lại toàn bộ mảng để kiểm tra xem arr[maj_index] có phải là phần tử chiếm đa số hay không.

arr[maj_index] là 4

4 xuất hiện 5 lần trong mảng nên 4 là phần tử chiếm đa số.

Làm theo các bước dưới đây để giải quyết vấn đề:

• Lặp qua từng phần tử và duy trì đếm tần suất của phần tử chiếm đa số (count) và chỉ số đa số maj_index.
• Nếu phần tử tiếp theo là tương tự thì tăng count và nếu phần tử tiếp theo không tương tự thì giảm count.
• Nếu count bằng 0 thì thay đổi maj_index thành phần tử hiện tại và đặt count quay trở về 1.
• Bây giờ tiếp tục duyệt qua mảng và tìm count của phần tử chiếm đa số đã tìm được.
• Nếu count lớn hơn một nửa kích thước mảng, trả về phần tử.
• Nếu không, trả về kết quả là mảng không có phần tử chiếm đa số.

Dưới đây là code mẫu để các bạn tham khảo:

# Program for finding out majority element in an array
 
# Function to find the candidate for Majority
 
 
def findCandidate(A):
    maj_index = 0
    count = 1
    for i in range(len(A)):
        if A[maj_index] == A[i]:
            count += 1
        else:
            count -= 1
        if count == 0:
            maj_index = i
            count = 1
    return A[maj_index]
 
# Function to check if the candidate occurs more than n/2 times
 
 
def isMajority(A, cand):
    count = 0
    for i in range(len(A)):
        if A[i] == cand:
            count += 1
    if count > len(A)/2:
        return True
    else:
        return False
 
# Function to print Majority Element
 
 
def printMajority(A):
    # Find the candidate for Majority
    cand = findCandidate(A)
 
    # Print the candidate if it is Majority
    if isMajority(A, cand) == True:
        print(cand)
    else:
        print("No Majority Element")
 
 
# Driver code
A = [1, 3, 3, 1, 2]
 
# Function call
printMajority(A)

Cách 4: Sử dụng Hashing

Trong Hashtable (cặp key-value), tại value duy trì count cho mỗi phần tử (key) và bất cứ khi nào count lớn hơn một nửa độ dài của mảng, trả về key đó (phần tử chiếm đa số).

Minh họa giải pháp:

arr[] = {3, 4, 3, 2, 4, 4, 4, 4}, n = 8

Tạo một hashtable cho mảng

3 -> 2
4 -> 5
2 -> 1

Duyệt qua toàn bộ hashtable

- Count cho 3 là 2, nhỏ hơn n/2 (4) do vậy nó không thể là phần tử chiếm đa số.
- Count cho 4 là 5, lớn hơn n/2 (4) do vậy 4 là phần tử chiếm đa số.

Kết luận 4 là phần tử chiếm đa số.

Làm theo các bước sau để giải quyết vấn đề:

• Tạo một hashtable chứa cặp key-value. Trong trường hợp này key là phần tử trong khi value là tuần suất xuất hiện của phần tử đó trong mảng.
• Duyệt qua toàn bộ mảng từ đầu đến cuối.
• Với mỗi phần tử trong mảng, thêm phần tử vào hashtable nếu phần tử chưa tồn tại dưới dạng một key, nếu không hãy nạp giá trị của key (array[i]) và tăng giá trị của value lên 1.
• Nếu count lớn hơn một nửa của kích thước mảng, trả về phần tử chiếm đa số và kết thúc chương trình.
• Nếu không, hãy trả về thông báo không tìm thấy phần tử chiếm đa số.

Dưới đây là code mẫu để các bạn tham khảo:

# Python3 program for finding out majority
# element in an array
 
def findMajority(arr, size):
    m = {}
    for i in range(size):
        if arr[i] in m:
            m[arr[i]] += 1
        else:
            m[arr[i]] = 1
    count = 0
    for key in m:
        if m[key] > size / 2:
            count = 1
            print("Majority found :-",key)
            break
    if(count == 0):
        print("No Majority element")
 
# Driver code
arr = [2, 2, 2, 2, 5, 5, 2, 3, 3]
n = len(arr)
 
# Function calling
findMajority(arr, n)
 
# This code is contributed by ankush_953

Cách 5: Sử dụng Sorting

Ý tưởng của phương pháp này là sắp xếp lại mảng. Sorting làm cho các phần tử tương tự trong mảng được xếp liền kề nhau do vậy hãy duyệt qua mảng và cập nhật count cho đến khi phần tử hiện tại vẫn giống với phần tử trước đó. Nếu tần suất của một phần tử lớn hơn một nửa kích thước của mảng, trả về phần tử chiếm đa số.

Minh họa giải pháp:

arr[] = {3, 4, 3, 2, 4, 4, 4, 4}, n = 8

Mảng sau khi Sorting => arr[] = {2, 3, 3, 4, 4, 4, 4, 4}, count = 1

Ở i = 1:

- arr[i] != arr[i – 1] => arr[1] != arr[0]
- count không lớn hơn n/2, do đó thiết lập lại count, count = 1

Ở i = 2:

- arr[i] == arr[i – 1] => arr[2] == arr[1] = 3
- count = count + 1 = 1 + 1 = 2

Ở i = 3

- arr[i] != arr[i – 1] => arr[3] != arr[2]
- count không lớn hơn n/2, do đó thiết lập lại count, count = 1

Ở i = 4

- arr[i] == arr[i – 1] => arr[4] == arr[3] = 4
- count = count + 1 = 1 + 1 = 2

Ở i = 5

- arr[i] == arr[i – 1] => arr[5] == arr[4] = 4
- count = count + 1 = 2 + 1 = 3

Ở i = 6

- arr[i] == arr[i – 1] => arr[6] == arr[5] = 4
- count = count + 1 = 3 + 1 = 4

Ở i = 7

- arr[i] == arr[i – 1] => arr[7] == arr[6] = 4
- count = count + 1 = 4 + 1 = 5

Do count của 4 lớn hơn n/2 nên 4 là phần tử chiếm đa số.

Làm theo các bước sau để giải quyết vấn đề:

• Sắp xếp mảng và tạo ra một biến count và temp với temp = INT_MIN.
• Duyệt qua toàn bộ các phần tử từ đầu đến cuối.
• Nếu phần tử hiện tại bằng với phần tử trước đó hãy tăng count.
• Nếu không, thiết lập count quay về 1.
• Nếu count lớn hơn một nửa kích thước của mảng, trả về phần tử chiếm đa số và dừng chương trình.
• Nếu không, trả về thông báo không có phần tử chiếm đa số.

Dưới đây là code mẫu để các bạn tham khảo:

# Python3 program to find Majority
# element in an array
 
# Function to find Majority element
# in an array
# it returns -1 if there is no majority element
def majorityElement(arr, n) :
     
    # sort the array in O(nlogn)
    arr.sort()  
    count, max_ele, temp, f = 1, -1, arr[0], 0
    for i in range(1, n) :
         
        # increases the count if the same element occurs
        # otherwise starts counting new element
        if(temp == arr[i]) :
            count += 1
        else :
            count = 1
            temp = arr[i]
             
        # sets maximum count
        # and stores maximum occurred element so far
        # if maximum count becomes greater than n/2
        # it breaks out setting the flag
        if(max_ele < count) :
            max_ele = count
            ele = arr[i]
             
            if(max_ele > (n//2)) :
                f = 1
                break
             
    # returns maximum occurred element
    # if there is no such element, returns -1
    if f == 1 :
        return ele
    else :
        return -1
 
# Driver code
arr = [1, 1, 2, 1, 3, 5, 1]
n = len(arr)
 
# Function calling
print(majorityElement(arr, n))
 
# This code is contributed by divyeshrabadiya07

Quản Trị Mạng hy vọng rằng bài viết này sẽ có ích đối với các bạn.