Java version of Majority Voting problem. http://goo.gl/d27jg
import java.math.BigDecimal; | |
import java.util.ArrayList; | |
import java.util.Arrays; | |
import java.util.List; | |
public class MajorityVoting { | |
public static String checkForWinner(List<String> votes) { | |
String winner = "Nobody"; | |
String[] votesArr = votes.toArray(new String[votes.size()]); | |
if (votesArr == null || votesArr.length == 0) { | |
return winner; | |
} | |
String[] sortedResult = quickSort(votesArr); | |
String currentVote = ""; | |
int voteCount = 0; | |
int maxVote = 0; | |
for (int index = 0; index < sortedResult.length; index++) { | |
if (currentVote == "") { | |
currentVote = sortedResult[index]; | |
} | |
if (currentVote.equalsIgnoreCase(sortedResult[index])) { | |
voteCount++; | |
} else { | |
if (voteCount > maxVote) { | |
maxVote = voteCount; | |
winner = currentVote; | |
} | |
voteCount = 1; | |
currentVote = sortedResult[index]; | |
} | |
} | |
return 2 * maxVote > sortedResult.length ? winner : "Nobody"; | |
} | |
private static String[] quickSort(String[] array) { | |
int len = array.length; | |
internalQuickSort(array, 0, len); | |
return array; | |
} | |
private static void internalQuickSort(String[] array, int left, int right) { | |
if (left < right) { | |
int pivot = (right + left) / 2; | |
int newSplitPoint = partition(array, left, right, pivot); | |
internalQuickSort(array, left, newSplitPoint - 1); | |
internalQuickSort(array, newSplitPoint + 1, right); | |
} | |
} | |
private static int partition(String[] array, int left, int right, int pivot) { | |
String temp = array[pivot]; | |
array[pivot] = array[left]; | |
array[left] = temp; | |
pivot = left; | |
for (int index = left + 1; index < right; index++) { | |
if (array[index].hashCode() < array[pivot].hashCode()) { | |
String tempVal = array[pivot]; | |
array[pivot] = array[index]; | |
array[index] = tempVal; | |
pivot = index; | |
} | |
} | |
return pivot; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment