程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Majority Number

Majority Number

編輯:C++入門知識

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

.

 

解法

    int majorityNumber(vector 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;
    }

算法解釋

一個思路,同時刪除兩個不同的數,那麼結果不會變

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved