Alibi

My Life is Getting Better

Leetcode[136, 137, 260] Single Number

10 Nov 2015

###Task1 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? ###Python

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        res = nums[0]
        for num in nums[1:]:
            res ^= num
        return res

###Java

public class Solution {
    public int singleNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
        	return 0;
        }

        int single = 0;
        for (int i = 0; i < nums.length; i++) {
        	single ^= nums[i];
        }

        return single;
    }
}

###Task2 Given an array of integers, every element appears three times except for one. Find that single one.

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

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        N = len(nums)
        temp = [0 for i in range(32)]
        for num in nums:
            for i in range(32):
                bit = (num >> i) & 1
                temp[i] += bit
                temp[i] %= 3
        res = 0
        if temp[31] % 3 == 0:
            for i in range(31):
                if temp[i] == 1:
                    res += 1 << i
        else:
            for i in range(31):
                if temp[i] == 0:
                    res += 1 << i
            res = -(res + 1)
        return res

###Java

public class Solution {
    public int singleNumber(int[] nums) {
        if (nums.length == 0 || nums == null) {
        	return 0;
        }

        int[] bits = new int[32];
        for (int i = 0; i < 32; i++) {
        	for (int j = 0; j < nums.length; j++) {
        		bits[i] += (nums[j] >>> i) & 1; // 将每个数同一位求和
        	}
        }

        int res = 0;
        for (int i = 0; i < 32; i++) {
        	res += (bits[i] % 3) << i; // 求和结果%3
        }

        return res;
    }
}

###Points

###Task3 Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note: The order of the result is not important. So in the above example, [5, 3] is also correct. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

###Python

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        N = len(nums)
        res = 0
        for num in nums:
            res ^= num
        last = res & (-res)
        left = 0
        right = 0
        for num in nums:
            if num & last == 0:
                left ^= num
            else:
                right ^= num
        return [left, right]

###Java

public class Solution {
    public int[] singleNumber(int[] nums) {
    	int[] res = new int[2];
        if (nums == null || nums.length == 0) {
        	return res;
        }
        int n = 0;
        res[0] = 0;
        res[1] = 0;
        for (int i = 0; i < nums.length; i++) {
        	n ^= nums[i];
        }

        n = n & (-n);
        for (int i = 0; i < nums.length; i++) {
        	if ((nums[i] & n) != 0) {
        		res[0] ^= nums[i];
        	} else {
        		res[1] ^= nums[i]; 
        	}
        }

        return res;
    }

    public static void main(String[] args) {
    	Solution sol = new Solution();
    	int[] nums = {1, 2, 2, 3, 4, 4, 5, 3};
    	int[] res = sol.singleNumber(nums);
    	for (int i: res) {
    		System.out.println(i);
    	}
    }
}

###Points

Related Posts