本文正在参加「金石方案 . 分割6万现金大奖」

前语：最近自己也开端体系的刷面试题了，算法是过不去的坎，希望自己能够坚持下去✊，同行的朋友们共勉。

题一：删去排序数组中的重复项

给你一个 升序排列 的数组 nums ，请你 原地 删去重复呈现的元素，使每个元素 只呈现一次 ，回来删去后数组的新长度。元素的 相对次序 应该保持 一致 。

留意：不要运用额定的空间，你有必要在 原地 修改输入数组 并在运用 O(1) 额定空间的条件下完结。

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]

解题思路：双指针

由于有约束条件，不能够运用额定空间，所以这儿不考虑运用字典来去重；在这儿能够运用双指针，即 前指针 和 后指针。

咱们能够经过遍历数组，判别两个相邻的指针所指向的值是否持平，假如不持平，则说明两者不重复，将后指针的值刺进到维护的下标下。假如持平，则不处理。

需求留意下标越界；

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

代码

func removeDuplicates(_ nums: inout [Int]) -> Int {
  var startIndex = 0
  for index in 0..<nums.count-1 {
    if nums[index] != nums[index+1] {
      startIndex+=1
      nums[startIndex] = nums[index+1]
    }
  }
  return startIndex+1
}

题二：翻转数组

给你一个数组，将数组中的元素向右轮转k 个方位，其中k 对错负数。

输入一：

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解说:
向右轮转 1 步: [7, 1, 2, 3, 4, 5, 6] 
向右轮转 2 步: [6, 7, 1, 2, 3, 4, 5] 
向右轮转 3 步: [5, 6, 7, 1, 2, 3, 4] 

输入二：

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解说： 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

解题思路：环形翻转、屡次翻转、临时数组

解法一：环形翻转

以输入一为例： 1,2,3,4,5,6,7, k = 3

1 ——> 4, 4 ——> 7, 7 ——> 3, 3 ——> 6, 6 ——> 2, 2 ——> 5, 5 ——> 1,

输出：5,6,7,1,2,3,4

环形翻转的思路就是以上流程的演变。

将第0位的值向右移动k，然后将k方位下的值移动到k + k方位下，顺次循环替换；
在替换前需求缓存后者的值，替换完之后，将操作的指针后移；

别的需求考虑到 nums.length%k=0 的状况，被整除了会在几个元素中循环；（被整除的状况下，仅在单个元素中来回翻转，并不能形成一个大环）

以输入二为例： -1, -100, 3, 99, k = 2

-1 ——> 3, 3 ——> -1, -1 ——> 3, …

输出：-1， -100， -1， 99

假如这儿没考虑到nums.length%k=0被整除的状况，就会呈现以上的问题，在这儿能够增加一个字典来缓存现已访问过的下标。假如呈现射中缓存的状况，就从它的下一位开端。

综合以上的状况能够得出以下的思路，

代码

func rotate(_ nums: inout [Int], _ k: Int) {
    var index = 0;
    var last = nums[index] // 前指针 用来赋值
    var temp = nums[index] // 后指针 用来先保存下一个方位的值
    var visiter = [Int:Int]() // 访问过的下标调集
    for _ in 0..<nums.count {
      // 移动下标核算
      // index = index+k < nums.count ? index+k : (index+k)%nums.count => index = (index+k)%nums.count
      index = (index+k)%nums.count
      // 假如访问过，需求打破小环；
      if visiter[index] != nil {
        while visiter[index] != nil {
          index+=1;
        }
        last = nums[index]
        index = (index+k)%nums.count
      }
      /// 惯例操作：
      /// 先把后指针的值缓存，
      /// 再把前指针的值刺进后指针方位，
      /// 再把缓存值回来给前指针，保证在下一轮替换前，index和前指针的值同步；
      temp = nums[index]
      nums[index] = last
      last = temp
      visiter[index] = index;
    }
  }

解法二：屡次翻转

这儿需求经过三次翻转，即可完结；

第一次：由于数组元素往右移动，所以肯定有元素会被移动到左面，这儿先做一次全体翻转；
第二次：经过移动值与长度值取余（k%n），得出分界线，前翻转规模（0，（k%n）-1），在此规模内的元素翻转；
第三次：最后将后翻转规模（k%n，n-1）内的元素进行翻转；

代码

func rotate(_ nums: inout [Int], _ k: Int) {
    let index = k%nums.count
    reverse(&nums, 0, nums.count-1)
    reverse(&nums, 0, index-1)
    reverse(&nums, index, nums.count-1)
}
func reverse(_ nums: inout [Int], _ start: Int, _ end: Int) {
    var start = start
    var end = end
    while (start < end) {
        nums.swapAt(start, end)
        start += 1
        end -= 1
    }
}

解法三：临时数组

运用一个临时数组寄存原数组的值，然后再把临时数组的值赋值给原数组，不过这儿还需求将每个元素往后移动k位。下标能够经过(i + k) % length来核算；

题三：存在重复元素

给你一个整数数组nums。假如任一值在数组中呈现至少两次，回来true；假如数组中每个元素互不相同，回来false。

示例 1：

输入： nums = [1,2,3,1]
输出： true

示例 2：

输入： nums = [1,2,3,4]
输出： false

解题思路：排序法、调集法

第一种思路：
假如给你的是一个排序后的数组，判别它是否存在重复元素是不是很简单，运用双指针判别就能够了。

第二种思路：
假如条件答应，运用键值（key-value）的调集去缓存数组中的元素，运用元素值当作key，假如下次被射中，同样能够知道数组存在重复元素。

第三种思路：
假如你知道无序调集set的话，你就知道无序调集不存在重复元素，那么这是不是也是一种思路呢？

二和三的思路都是凭借调集的形式，仅仅办法上有些不同。

解法一：排序法

将一个数组排序后，经过双指针遍历数组，若两个相邻的指针（i，i+1）数值相同，则存在重复元素，回来true，假如不重复，则指针一起向后移动；
假如遍历完也没有重复，回来false。

代码

func containsDuplicate2(_ nums: [Int]) -> Bool {
    var newNums = nums
    newNums.sort()
    for i in 0..<nums.count-1 {
        if newNums[i] == newNums[i+1] {
            return true
        }
    }
    return false
}

解法二：调集法

运用字典的特性，能够将数组元素的值作为字典的key。当你发现key键下现已存在时，证明现已存在重复数据。

代码

func containsDuplicate(_ nums: [Int]) -> Bool {
    var numDict = [Int: Int]()
    for num in nums {
        if numDict[num] == nil {
            numDict[num] = num
        } else {
            return false
        }
    }
    return true
}

题四：只呈现一次的数字

给你一个 非空 整数数组 nums ，除了某个元素只呈现一次以外，其余每个元素均呈现两次。找出那个只呈现了一次的元素。

你有必要设计并完成线性时刻复杂度的算法来处理此问题，且该算法只运用常量额定空间。

示例 1 ：

输入：nums = [2,2,1]
输出：1

示例 2 ：

输入：nums = [4,1,2,1,2]
输出：4

解题思路：位运算

假如说你只看标题，没有留意下面的要求，那么你可能会觉得就这。。。

找出不重复的元素并不难，即便是运用线性时刻复杂度相同也有很多办法能够处理。可是难在该算法只运用常量额定空间。也就是咱们不必凭借外部空间去完成。

话说回来，有什么好的解题思路呢，答案就是位运算。经过运用位运算中的异或操作符即可。

异或：

数学符号：⊕
编程符号：^

任何数和它自己异或都是0， a ⊕ a = 0
任何数和0异或都是它自己， a ⊕ 0 = a
异或运算满意交换律和结合律， a ⊕ b ⊕ a = a ⊕ a ⊕ b = 0 ⊕ b = b

代码

func singleNumber(_ nums: [Int]) -> Int {
    var result = 0
    for num in nums {
        result ^= num
    }
    return result
}