Android Code Snippet Majority element in array

sub name : Majority
Author : (see link below)
Description: This algorithm finds the majority element in an array - meaning it appears at least half of the array size, in one scan of the array (+1 to check...).
In the example array, the majority element is 2 which appear 8 times.
Found here http://www.keithschwarz.com/interesting/code/?dir=majority-element
B4X:
Sub AppStart (Form1 As Form, Args() As String)
    'MainForm = Form1
    'MainForm.RootPane.LoadLayout("Layout1") 'Load the layout file.
    'MainForm.Show
    Dim data() As Int = Array As Int (1,2,2,2,2,2,3,1,2,0,0,2,2,0,3)
    Dim k As Int = majority(data)
    If k = -999 Then Log("not found") Else Log(k)
End Sub

Sub majority(data() As Int) As Int
Dim guess As Int = data(0)
Dim count As Int = 1
For i = 1 To data.Length-1  ' first pass to find result
    If count = 0 Then guess = data(i)
    If data(i) = guess Then
        count = count + 1
    Else
        count = count - 1
    End If
Next
count = 0  ' second pass to check result by counting
For i = 0 To data.Length - 1
    If data(i) = guess Then count = count + 1
Next
If count >= data.Length/2 Then
    Return guess
Else
    Return -999
End If
End Sub

Tags: Majority
 
Top