LeetCode题解136.single-number

题目地址

https://leetcode.com/problems/single-number/description/

题目描述

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?

思路

根据题目描述，由于加上了时间复杂度必须是 O(n)，并且空间复杂度为 O(1)的条件，因此不能用排序方法，也不能使用 map 数据结构。

我们可以利用二进制异或的性质来完成，将所有数字异或即得到唯一出现的数字。

关键点

1. 异或的性质
   两个数字异或的结果a^b是将 a 和 b 的二进制每一位进行运算，得出的数字。 运算的逻辑是
   如果同一位的数字相同则为 0，不同则为 1

2. 异或的规律

• 任何数和本身异或则为0

• 任何数和 0 异或是本身

3. 很多人只是记得异或的性质和规律，但是缺乏对其本质的理解，导致很难想到这种解法（我本人也没想到）

4. bit 运算

代码

• 语言支持：JS，C++，Python

JavaScrip Code：

/*
 * @lc app=leetcode id=136 lang=javascript
 *
 * [136] Single Number
 *
 * https://leetcode.com/problems/single-number/description/
 *
 * algorithms
 * Easy (59.13%)
 * Total Accepted:    429.3K
 * Total Submissions: 724.1K
 * Testcase Example:  '[2,2,1]'
 *
 * 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
 *
 *
 */
/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
  let ret = 0;
  for (let index = 0; index < nums.length; index++) {
    const element = nums[index];
    ret = ret ^ element;
  }
  return ret;
};

C++：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        auto ret = 0;
        for (auto i : nums) ret ^= i;
        return ret;
    }
};

// C++ one-liner
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        return accumulate(nums.cbegin(), nums.cend(), 0, bit_xor<int>());
    }
};

Python Code:

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        single_number = 0
        for num in nums:
            single_number ^= num
        return single_number

延伸

有一个 n 个元素的数组，除了两个数只出现一次外，其余元素都出现两次，让你找出这两个只出现一次的数分别是几，要求时间复杂度为 O(n) 且再开辟的内存空间固定(与 n 无关)。

和上面一样，只是这次不是一个数字，而是两个数字。还是按照上面的思路，我们进行一次全员异或操作，
得到的结果就是那两个只出现一次的不同的数字的异或结果。

我们刚才讲了异或的规律中有一个任何数和本身异或则为0， 因此我们的思路是能不能将这两个不同的数字分成两组 A 和 B。
分组需要满足两个条件.

1. 两个独特的的数字分成不同组

2. 相同的数字分成相同组

这样每一组的数据进行异或即可得到那两个数字。

问题的关键点是我们怎么进行分组呢？

由于异或的性质是，同一位相同则为 0，不同则为 1. 我们将所有数字异或的结果一定不是 0，也就是说至少有一位是 1.

我们随便取一个， 分组的依据就来了， 就是你取的那一位是 0 分成 1 组，那一位是 1 的分成一组。
这样肯定能保证2. 相同的数字分成相同组, 不同的数字会被分成不同组么。 很明显当然可以， 因此我们选择是 1，也就是
说两个独特的的数字在那一位一定是不同的，因此两个独特元素一定会被分成不同组。

Done！

LeetCode题解1020.number-of-enclaves

题目地址 https://leetcode-cn.com/problems/number-of-enclaves/ 题目描述 给出一个二维数组 A，每个单元格为 0（代表海）或 1（代表陆地）。 移动是指在陆地上从一个地方走到另一个地方（朝四个方向之一）或离开网格的边界。 返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。   示例 1： 输入…

LeetCode题解堆排序和快速排序

堆排序和快速排序都是时间复杂度$O(nlogn)$ 的算法，其中 n 为数据规模。 那么两者谁更快呢？ 为什么？题解：快排最坏情况下是O(n^2)，平均和最好是O(nlogn) ，堆排序始终为O(nlogn)，还是堆排序快吧

LeetCode题解斜着遍历

遍历是算法的基础。 我们平时看到的 DFS 和 BFS 都是搜索， 而搜索的核心就是遍历，而关键点就是遍历的方式。 从根本上说动态规划也是枚举所有的可能，而枚举就需要用到遍历。 而平时遍历一个二维数组 martrix 的时候， 我们习惯的方式是按行从左到右或者从右到左遍历。 少有情况是按照列遍历， 更少有情况是斜着遍历。那么这次就考考你， 怎么斜着遍历一个二…

LeetCode题解1297.maximum-number-of-occurrences-of-a-substring

题目地址（1297. 子串的最大出现次数） https://leetcode-cn.com/problems/maximum-number-of-occurrences-of-a-substring 题目描述 给你一个字符串 s ，请你返回满足以下条件且出现次数最大的 任意 子串的出现次数： 子串中不同字母的数目必须小于等于 maxLetters 。 子串的…

LeetCode题解砝码的最小数量

假设有三种重量的砝码，2g、3g、7g，对于任意重量物品，请设计一个函数getResult(weight)，接收一个参数weight，返回所需砝码的最小数量。输入示例：const weight = 100;输出示例：getResult(weight) // 15 其中7g的14个，2g的1个题解：```phpfunction getResult($weigh…