Vic - 1 year ago 65

Java Question

I am trying to use Java 8 to rewrite the implementation of Moore’s Voting Algorithm to find the Majority Element in an array.

The Java 7 implementation will be something like this:

`public int findCandidate(int[] nums) {`

int maj_index = 0, count = 1;

for(int i=1; i<nums.length;i++){

if(count==0){

count++;

maj_index=i;

}else if(nums[maj_index]==nums[i]){

count++;

} else {

count--;

}

}

return nums[maj_index];

}

The method I can think of is using stream reduce to get the final result

`public int findCandidate(int[] nums) {`

int count = 1;

Arrays

.asList(nums)

.stream()

.reduce(0, (result, cur) -> {

if (count == 0) {

result = cur;

count++;

} else if (result == cur){

count++;

} else {

count --;

}

});

return result;

}

But this method have compile error, besides, it also break the functional purist, I encounter this situation many times, so what is the best way to deal with the global variable inside the lambda expression.

Answer Source

So just like I told you within my comment, it is not ok to use mutable objects within your lambda expressions. But in your case, if you really want to apply the same algorithm, it'll be difficult.

Here's one that will do the same as what you want, if no majority is found, it returns `-1`

```
public static int findCandidate(int ... nums) {
Map<Integer, List<Integer>> map =
Arrays.stream(nums)
.boxed()
.collect(Collectors.groupingBy(x -> x));
int value =
map
.entrySet().stream()
.max((e1, e2) -> Integer.compare(e1.getValue().size(), e2.getValue().size()))
.map(e -> e.getKey())
.get();
int result = map.get(value).size();
return result > nums.length / 2 ? value : -1;
}
```