leetcode 136. Single Number

題目原文

Given an array of integers, every element appearstwiceexcept for one. Find that single one.

Note:

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

題意概述

就是說一堆數字序列，基本上每個數字都出現了兩次，只有一個數字出現了一次。請找出這個數字。並且不分配額外內存。題目的tag是Hash table、Bit manipulate。這題並不難。。水的很，雖然題目提示了用hash和位操作來解。。但本著練習STL的目的，我還是另辟蹊徑，使用了STL的accumulate算法來解題。

解題思路

先把序列排序（NlogN），然後相等的元素就相鄰了。這時因為正負數可以互相抵消。只要我們采取A-B+C-D+E-F……這種加法，最後沒有被抵消掉的肯定就是那個落單的元素了。 accumulate算法正是為了連續的累“加”操作准備的，只有我們自定義這個加法邏輯，該題很容易AC。

AC代碼：

struct OP {
    int operator() (int x, int y)
    {
        i*=-1;
        return x+i*y;
    }
    OP():i(-1){};
    int i;
};
class Solution {
public:
    int singleNumber(vector& nums) {
        sort(nums.begin(), nums.end());
        return accumulate(nums.begin(), nums.end(), 0, OP());
    }
};

怎麼樣，簡單吧。