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
Tags: 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