Swift 3.0

//
//  E_268_MissingNumber.swift
//  AlgorithmLeetCode
//
//  Created by okerivy on 2017/3/9.
//  Copyright © 2017年 okerivy. All rights reserved.
//  https://leetcode.com/problems/missing-number

import Foundation




// MARK: - 题目名称: 268. Missing Number

/* MARK: - 所属类别:
 标签: Array, Math, Bit Manipulation
 
 相关题目:
  (H) First Missing Positive
  (E) Single Number
  (M) Find the Duplicate Number
 
 */

/* MARK: - 题目英文:
 
 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?
 
 Credits:
 Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
 
 */


/* MARK: - 题目翻译:
 
 给定一个数组，数组包含 n 个取自 0, 1, 2, ..., n 的不同的数字，从数组中找到丢失的那个数字。
 
 例如：给定 nums = [0, 1, 3] 返回 2.
 
 注意：
 你的算法应当使用线性的时间复杂度（即时间复杂度为O(n)）。你能够只使用常量的额外空间来解决这题吗？
 
 */



/* MARK: - 解题思路:
 
 1.
 从 0, 1, 2, ..., n 中取 n 个不同的数字组成数组 nums，寻找丢失的那个数字，非常自然的想法就是将 0, 1, 2, ..., n 加和之后，减去数组 nums 的和就得到了丢失的那个数字。
 
 思路非常简单。但是为了避免加和造成的溢出，
 这里有一个小技巧：即不需要将两个数组先加起来之后再做减法，可以边加边减。
 例如 数组
 数字     0   1   3   4   5   6   7   8   // 缺失的是 2
 下标     0   1   2   3   4   5   6   7   // 8个元素
 
 进行相加相减运算 上下全部进行 (i - nums[i])
 0-0+1-1+3-2+4-3+5-4+6-5+7-6+8-7 = 0-0 1-1 3-3 4-4 5-5 6-6 7-7 2-8 = 2-8
 
 (i - nums[i]) = 2-8
 
 可以看到 2 已经出来了 因为 nums.count = 8 所以再次相加一次 ans + (i - nums[i])
 nums.count + 2-8 = 8 + 2-8 = 2
 
 
 2.
 其基本思想是利用异或XOR运算。我们都知道一个a^b^b =a，这意味着相同数量的两异或操作将消除数量和揭示原数。
 在这个解决方案中，我运用异或XOR操作的指标和数组的值。
 在一个没有缺数字完整的阵列，指标值应完全对应（nums[index] = index），所以在丢失数组，剩下的最后是失踪数字。
 
 例如 数组
 数字     0   1   3   4   5   6   7   8   // 缺失的是 2
 下标     0   1   2   3   4   5   6   7   // 0..7 有8个元素
 
 进行异或运算 上下全部进行 (i ^ nums[i])
 0^0^1^1^3^2^4^3^5^4^6^5^7^6^8^7 = 0^0^1^1^3^3^4^4^5^5^6^6^7^7^8^2 = 8^2
 
 (i ^ nums[i]) = 8^2
 
 可以看到 2 已经出来了 因为 xor = nums.count = 8 所以再次异或一次 xor ^ (i ^ nums[i])
 8^2^nums.count = 8^2^8 = 2
 
 
 ---------------------------------
 异或是一种基于二进制的位运算，用符号XOR或者 ^ 表示，
 
 其运算法则是对运算符两侧数的每一个二进制位，同值取0，异值取1。
 
 异或的性质
 交换律：a ^ b = b ^ a
 结合律：a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c
        d = a ^ b ^ c 可以推出 a = d ^ b ^ c
 自反性：a ^ b ^ a = b
 
 
 
 算法题目
 
 ①1-1000放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现一次。每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空间，能否设计一个算法实现？
 
 前面提到异或具有交换律和结合律，所以1^2^...^n^...^n^...^1000，无论这两个n出现在什么位置，都可以转换成为1^2^...^1000^(n^n)的形式。
 
 其次，对于任何数x，都有x^x=0，x^0=x。
 
 所以1^2^...^n^...^n^...^1000 = 1^2^...^1000^(n^n)= 1^2^...^1000^0 = 1^2^...^1000（即序列中除了n的所有数的异或）。
 
 令，1^2^...^n^..^1000（序列中包含一个n）的结果为T
 则1^2^..^n^..^n^..^1000（序列中包含2个n）的结果就是T^n。
 T^(T^n)=n。
 
 所以，将所有的数全部异或，得到的结果与1^2^3^...^1000的结果进行异或，得到的结果就是重复数。
 
 */


/* MARK: - 复杂度分析:
 间复杂度是O(n)，空间复杂度为O(1)
 
 */


// MARK: - 代码:
private class Solution {
    
    // 加法求和
    func missingNumber(_ nums: [Int]) -> Int {
        var ans = 0
        for i in 0..<nums.count {
            ans = ans + i - nums[i]
        }
        ans += nums.count
        return ans
    }
    
    // 异或运算
    func missingNumber2(_ nums: [Int]) -> Int {
        var xor = nums.count
        for i in 0..<nums.count {
            xor = xor ^ i ^ nums[i];
        }
        return xor;
    }

}



// MARK: - 测试代码:
func missingNumber() {
  
    print(Solution().missingNumber([0, 1, 3, 4, 5, 6, 7]))
    print(Solution().missingNumber([1, 2, 3, 4, 5]))
    print(Solution().missingNumber([0, 1, 2, 4, 5]))
    print(Solution().missingNumber([5, 1, 2, 0, 4]))

}