public int majorityElement(int[] nums) {
        int count = 1;
        int majorityIndex = 0;

        //Find a majority candidate
        for (int i=0; i<nums.length; i++) {
            if (nums[majorityIndex] == nums[i])
                count = count + 1;
            else
                count = count - 1;

            if (count == 0) {
                majorityIndex = i;
                count = 1;
            }
        }

        //Check if the majority candidate is really the majority element
        int count2 = 0;
        for (int i=0; i<nums.length; i++) {
            if (nums[i] == nums[majorityIndex])
                count2 = count2 + 1;
        }

        if (count2 >= nums.length/2)
            return nums[majorityIndex];
        else
            return -1;

    }