```
public class Solution {
public int majorityElement(int[] num) {
if(num.length == 1) return num[0];
int[] rst = new int[1];
getMajority(num, 0, num.length-1, rst);
return rst[0];
}
public void getMajority(int[] num, int l, int r, int[] rst){
if(l >= r){
rst[0] = num[r];
return;
}
int m = r - (r-l)/2;
// check if num[m] is majority element in num
int count = 0;
for(int i = 0; i < num.length; i++){
if(num[i] == num[m])
count++;
}
if(count > num.length/2){
rst[0] = num[m];
return;
}
getMajority(num, l, m-1, rst);
getMajority(num, m+1, r, rst);
}
```

}

time & space complexity: nlgn. O(n) solution seems hard to come up during an interview.