你知道“二分”，那你知道“三路切分”吗？

在这里核心就是算法思想叫做"三路切分"。 “三路切分” 曾是 EMC 面试中的常客，这个名词听起来很高大上，但是简单来说就是将数组切分成三部分。 我再回忆一下“快速排序”算法。

// 交换数组中两个元素的值 
function swap(a, i, j) {
  const temp = a[i];
  a[i] = a[j];
  a[j] = temp;
}
function qsort(a, b, e) {
  // 边界处理
  if (b >= e || b + 1 >= e) {
    return;
  }
  
  // 第一步：划分子结构
  const mid = b + ((e - b) >> 1);
  
  // 第二步：找到根节点，获取信息
  const x = a[mid];
  let l = b;
  let i = b;
  let r = e - 1;
  
  while(i  r 的时候，[i, r] 才是空集。原本的四个区间，变成三个区间。[0, l)  小于 x 的区间[l, i)  等于 x 的区间[i, length) 大于 x 的区间。注意此时由于 i > r，实际上 i = r + 1，那么区间 (r, length) 就是 [i, length)。 由于最终状态是将一个乱序的数组切分成三部分，所以这个方法又叫三路切分。接下来我们看一个例子：列1：只出现一次的数字给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。示例 1 ：
 
输入：nums = [2,2,1]
输出：1
示例 2 ：
 
输入：nums = [4,1,2,1,2]
输出：4
示例 3 ：
 
输入：nums = [1]
输出：1
这道题目想想用“三路切分”如何实现？
任意选中一个数字 x ，将数组分成三份，那么是不是会出现三种情况？
 
第一种：只出现一次的数字在 x 左边，那么左边区域的长度为奇数，因为其他的数都是出现了两次。
第二种：选中的 x 就是只出现一次的数组，左右两边区间长度都为偶数。
第三种：只出现一次的数在右边，那么右区间的长度为奇数。
 
通过分析可知 3 种情况中，只有第二种情况得到了结果。而第一种情况只出现 1 次的数在左区间时，只需要递归地处理左区间；第三种情况只出现 1 次的数在右区间时，只需要递归地处理右区间。
function swap(A, i, j) {
  const t = A[i];
  A[i] = A[j];
  A[j] = t;
}
function threeSplit(a, b, e) {
  // 边界情况
  if (b >= e) {
      return 0;
    }
  /*********************核心代码****************************/
  // 第一步：划分子结构
  const mid = b + ((e - b) >> 1);
  // 第二步：获取根节点信息 x
  const x = a[mid];
  // 根据 x 将数组一分为三 【三路切分】
  let l = b;
  let i = b;
  let r = e - 1;
  while(i