This problem could be solved by two different ways.1. use a HashMap to record each integer‘s appearance. to get the final target value, we could use two methods.1.1 scan through the HashMap to get the key of maximum appearance.1.2 use two varibles: target and max_count, to keep track of the max_count and target all the time.if (map.get(num[i]) > max_count) {    target = num[i];    max_count = map.get(num[i]);}2. use the property given by the problem: the majority element appears more than N/2 times.Since the majority element appears more than N/2 times, we could the following pattern:2.1. initialize the target as num[0] and count as 0.int target = num[0];int count = 1;2.2. once we encounter a new element, we compare it with target2.2.1  iff the new element = target, we increase the count by 1;and if the count larger than num.length/2(seldom), we could return the target directly.2.2.2  iff the new element != target, we decrease the count by 1;if (target != num[i]) {    count--;} else{    count++;    if (count > num.length/2)        return target;}The key idea behind this solutin is that: the majority appears more than N/2. Even the array is not sorted, once we detect a inequality between two elements(not integer, the same integer could have multiple elements), we remove the two elements from the candidate list. Thus we could finally leave with the element with the most apperance.Note: once we exclude all elements ahead of num[i] (when count is equal to 0), we need to pick num[i] into the candidate list to continue the invariant:if (count == 0) {    target = num[i];    count = 1;    continue;}Key: we have a condidate list(only a single element)!!!!All we care is the element‘s value!

public class Solution {    public int majorityElement(int[] num) {        if (num == null || num.length == 0)            return -1;        int target = 0;        int max_count = 0;        HashMap<Integer, Integer> map = new HashMap<Integer, Integer> ();        for (int i = 0; i < num.length; i++) {            if (map.containsKey(num[i])) {                map.put(num[i], map.get(num[i])+1);            } else{                map.put(num[i], 1);            }            if (map.get(num[i]) > max_count) {                target = num[i];                max_count = map.get(num[i]);            }        }        return target;    }}

public class Solution {    public int majorityElement(int[] num) {        if (num == null || num.length == 0)            return -1;        int target = num[0];        int count = 1;        for (int i = 1; i < num.length; i++) {            if (count == 0) {                target = num[i];                count = 1;                continue;            }            if (target != num[i]) {                count--;            } else{                count++;                if (count > num.length/2)                    return target;            }        }         return target;    }}