首页 > 代码库 > Majority Number

Majority Number

    • 题目描写叙述
    • 链接地址
    • 解法
    • 算法解释

题目描写叙述

Given an array of integers, the majority number is the number that occurs more than half of the size of the array. Find it..

Example

Given [1, 1, 1, 1, 2, 2, 2], return 1

Challenge

O(n) time and O(1) extra space

.

链接地址

http://www.lintcode.com/en/problem/majority-number/

解法

    int majorityNumber(vector<int> nums) {
        // write your code here
        int ret, num = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (num == 0) {
                ret = nums[i];
                num++;
            } else {
                if (nums[i] == ret) {
                    num++;
                } else {
                    num--;
                }
            }
        }
        return ret;
    }

算法解释

一个思路。同一时候删除两个不同的数。那么结果不会变

<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
    ‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
  • ‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>

Majority Number