ARTS打卡：第八周

每周完成一个ARTS：

Algorithm：每周至少做一个 leetcode 的算法题

Review：阅读并点评至少一篇英文技术文章

Tip：学习至少一个技术技巧

Share：分享一篇有观点和思考的技术文章

Algorithm

136. Single Number（Easy）

Given a non-empty 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?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

Input: [4,1,2,1,2]
Output: 4

@DevDocsleetcode.com/problems/single-number

题意：
给一个不空的整型数组，除一个元素之外，其余每个元素都会出现两次，找到那个独立的元素。
注意：你的算法应该具有线性运行时复杂度。你能不用额外的内存来实现它吗？

解题思路1：
根据题意，我们可以知道，输入是一个不为空的整型数组，且这个数组长度一定是奇数的，且那个不重复的元素一定是奇数位的元素，那么我们可以先对数组进行排序，然后遍历数组，假设这个数组为 nums，当 nums[i] != nums[i + 1] && nums[i] != nums[i - 1] 时，nums[i] 即为那个不重复的元素，当然首尾元素要单独进行判断。

代码如下：

public int singleNumber(int[] nums) {
    if (nums.length == 1) {
        return nums[0];
    }
    Arrays.sort(nums);
    if (nums[0] != nums[1]) {
        return nums[0];
    }
    for (int i = 2; i < nums.length - 1; i += 2) {
        System.out.println(i);
        if (i != nums.length - 1 && nums[i] != nums[i + 1] && nums[i] != nums[i - 1]) {
            return nums[i];
        }
    }
    return nums[nums.length - 1];
}

结果：
Runtime: 3 ms, faster than 42.26% of Java online submissions for Single Number.
Memory Usage: 37.9 MB, less than 77.61% of Java online submissions for Single Number.

解题思路2：
还有一种解算，我在讨论区看到的，着实让我眼前一亮，从而打开了新世界的大门。
利用 XOR 逻辑异或去做，因为 0 ^ N = N，N ^ N = 0，所以只需以0为初始值，去遍历数组，进行异或运算，最后就能得到那个唯一的不同值。

代码如下：

class Solution {
    /**
     * 哇，这个解法完全没想到，打开新世界的大门
     * 使用 XOR 逻辑异或 去做
     * 0 ^ N = N
     * N ^ N = 0
     * 所以只需遍历进行异或，就能得到那个唯一的不同值
     * @param nums
     * @return
     */
    public int singleNumber(int[] nums) {
        int a = 0;
        for (int i : nums) {
            a ^= i;
        }
        return a;
    }
}

结果：
Runtime: 0 ms, faster than 100.00% of Java online submissions for Single Number.
Memory Usage: 38.2 MB, less than 73.27% of Java online submissions for Single Number.

时间复杂度：O(n)
空间复杂度：O(1)