Doing something you intrinsically are enthusiastic with.

2016年2月22日 星期一

Leetcode- Missing Number in Java

凌晨3:14 Posted by Unknown No comments


題目:

Given an array containing n distinct numbers taken
 from 0, 1, 2, ..., n, find the one that is missing from the array.
For example,
Given nums = [0, 1, 3] return 2.
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

如果要跑Linear Runtime的話
很明顯就是不能夠先排序再去找了
排序最快平均也會到O(nlogn)
這種時候還是回來想想其他辦法

對於這種排除某個元素的問題
最好是可以想看看如何使用bit manipulation 來做

XOR這個東西很好用
可以遇到不同的東西就變1 
其實就是變相讓它融入你
如果那個東西剛好是你沒有的
那麼就會有種補缺漏的效果

根據XOR的簡單用法
A XOR B=C
C XOR A=B
所以
問題測資 XOR MISSING NUM=全部沒缺
全部沒缺 XOR 闕漏部分=MISSING NUMBER

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int res = 0;
        for (int i = 0; i < nums.size(); ++i) {
            res ^= (i + 1) ^ nums[i];
        }
        return res;
    }
};

0 意見:

張貼留言