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

LeetCode練習-singleNumber

編輯:C++入門知識

LeetCode練習-singleNumber


題目意思:

一個數值數組中,大部分的數值出現兩次,只有一個數值只出現過一次,求編程求出該數字。
要求,時間復雜度為線性,空間復雜度為O(1).

解題思路:

1.先排序,後查找。

由於排序的最快時間是O(nlogn), 所以這種方法不能滿足時間的要求。

2.其它技巧來解決:

根據基本的計算機組成原理的知識,采用”異或運算“來巧妙的完成,

異或運算很簡單:

0^0=0
1^1=0
1^0=0^1=1

也就是說相同則為0,不同則為1.

所以任何相同的兩個數的異或運算值結果為0。

0與任何數進行異或運算等於該值。

所以,我們只需要將所有的數字進行異或運算一次(O(N)),它的結果就是我們要找的,只出現過一次的值。

#include 
#include
using namespace std;

//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?
class Solution {
public:
    int singleNumber(vector& nums)
    {
        vector::iterator it;
        it=nums.begin();
        int sum=*it;
        for (it=nums.begin()+1;it nums;
    std::vector::iterator it;
    it = nums.begin();
    int t;
    while(cin>>t)
    {
        it =nums.insert (it,t);
    }

    cout << instance.singleNumber(nums) << endl;
    return 0;
}

 

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