package org.wesome.dsalgo;
import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;
import java.util.HashMap;
import java.util.Map;
@Data
@AllArgsConstructor
@NoArgsConstructor
class MajorityVote {
int vote;
int count;
}
public class BoyerMooreMajorityVote {
public static MajorityVote boyerMooreMajorityVote(int[] arr) {
Map<Integer, Integer> map = new HashMap<>();
for (int i : arr) {
map.put(i, map.getOrDefault(i, 0) + 1);
}
int average = arr.length / 2;
MajorityVote majorityVote = null;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() > average) {
majorityVote = new MajorityVote(entry.getKey(), entry.getValue());
}
}
return majorityVote;
}
}
package org.wesome.dsalgo;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import static org.wesome.dsalgo.BoyerMooreMajorityVote.boyerMooreMajorityVote;
public class BoyerMooreMajorityVoteTest {
@Test
void boyerMooreMajorityVoteTest1() {
int[] arr = {4, -6, 3, -1, 4, 2, 7};
Assertions.assertNull(boyerMooreMajorityVote(arr));
}
@Test
void boyerMooreMajorityVoteTest2() {
int[] arr = {1, 8, 7, 4, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2};
MajorityVote majorityVote = boyerMooreMajorityVote(arr);
Assertions.assertAll(() -> Assertions.assertEquals(1, majorityVote.getVote()),
() -> Assertions.assertEquals(9, majorityVote.getCount()));
}
}
plugins {
id 'java'
id "io.freefair.lombok" version "6.2.0"
}
group = 'org.wesome'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = JavaVersion.VERSION_1_8
configurations {
compileOnly {
extendsFrom annotationProcessor
}
}
repositories {
mavenCentral()
}
dependencies {
testImplementation 'org.junit.jupiter:junit-jupiter:5.6.2'
}
test {
useJUnitPlatform()
}