程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LeetCode 136 Single Number(只出現一次的數字)

LeetCode 136 Single Number(只出現一次的數字)

編輯:關於C++

翻譯

給定一個整型數組,除了某個元素外其余元素均出現兩次。找出這個只出現一次的元素。

備注:
你的算法應該是一個線性時間復雜度。你可以不用額外空間來實現它嗎?

原文

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

分析

請參照上一題:LeetCode 260 Single Number III(只出現一次的數字3)(*)

還有一道與之對應的題:LeetCode 137 Single Number II(只出現一次的數字 II)(*)

代碼

class Solution {
public:
 unsigned int FindFirstBigIs1(int num) {
    int indexBit = 0;
    while (((num & 1) == 0) && (indexBit < 8 * sizeof(int))) {
        num = num >> 1;
        ++indexBit;
    }
    return indexBit;
}

int singleNumber(vector& nums) {
    if (nums.size() <= 0) return NULL;

    int resultExclusiveOR = 0;
    for (int i = 0; i < nums.size(); ++i)
        resultExclusiveOR ^= nums[i];

    unsigned int indexOf1 = FindFirstBigIs1(resultExclusiveOR);

    int singleNum = 0;
    for (int j = 0; j < nums.size(); ++j) {
            singleNum ^= nums[j];
    }
    return singleNum;
}
};
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved