昨天同学问到，于是立即帮忙想了一个方法。

问题是，给定一个无序的数组，找出与中位数最接近的k个数，要求O(n)的复杂度。

思路是这样的：


首先，我们需要知道利用线性时间选择可以在O(n)的时间内求出无序数组的中位数。


（1）O(n)求出无序数组中位数
（2）把数组里的所有数依次减去中位数并取绝对值，得到一个新的数组。这个数组的每个数表示其与中位数的距离的大小。复杂度O(n)。
（3）利用线性时间选择的方法，可以在O(n)时间求出第k个数，此时其左边的所有数都比k小，即可得到k个最小的数。
（4）k个最小的数所对应的原数就是与中位数最近的k个数。


至此完成要求。

题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

分析：这是一道很新颖的关于位运算的面试题。

首先我们考虑这个问题的一个简单版本：一个数组里除了一个数字之外，其他的数字都出现了两次。请写程序找出这个只出现一次的数字。

这个题目的突破口在哪里？题目为什么要强调有一个数字出现一次，其他的出现两次？我们想到了异或运算的性质：任何一个数字异或它自己都等于0。也就是说，如果我们从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现依次的数字，因为那些出现两次的数字全部在异或中抵消掉了。

有了上面简单问题的解决方案之后，我们回到原始的问题。如果能够把原数组分为两个子数组。在每个子数组中，包含一个只出现一次的数字，而其他数字都出现两次。如果能够这样拆分原数组，按照前面的办法就是分别求出这两个只出现一次的数字了。

我们还是从头到尾依次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数字的异或结果。因为其他数字都出现了两次，在异或中全部抵消掉了。由于这两个数字肯定不一样，那么这个异或结果肯定不为0，也就是说在这个结果数字的二进制表示中至少就有一位为1。我们在结果数字中找到第一个为1的位的位置，记为第N位。现在我们以第N位是不是1为标准把原数组中的数字分成两个子数组，第一个子数组中每个数字的第N位都为1，而第二个子数组的每个数字的第N位都为0。

现在我们已经把原数组分成了两个子数组，每个子数组都包含一个只出现一次的数字，而其他数字都出现了两次。因此到此为止，所有的问题我们都已经解决。

基于上述思路，我们不难写出如下代码：

///

// Find two numbers which only appear once in an array

// Input: data - an array contains two number appearing exactly once,

//               while others appearing exactly twice

//        length - the length of data

// Output: num1 - the first number appearing once in data

//         num2 - the second number appearing once in data

///

void FindNumsAppearOnce(int data[], int length, int &num1, int &num2)

{

      if (length < 2)

            return;

 

      // get num1 ^ num2

      int resultExclusiveOR = 0;

      for (int i = 0; i < length; ++ i)

            resultExclusiveOR ^= data[i];

 

      // get index of the first bit, which is 1 in resultExclusiveOR

      unsigned int indexOf1 = FindFirstBitIs1(resultExclusiveOR);

 

      num1 = num2 = 0;

      for (int j = 0; j < length; ++ j)

      {

            // divide the numbers in data into two groups,

            // the indexOf1 bit of numbers in the first group is 1,

            // while in the second group is 0

            if(IsBit1(data[j], indexOf1))

                  num1 ^= data[j];

            else

                  num2 ^= data[j];

      }

}

 

///

// Find the index of first bit which is 1 in num (assuming not 0)

///

unsigned int FindFirstBitIs1(int num)

{

      int indexBit = 0;

      while (((num & 1) == 0) && (indexBit < 32))

      {

            num = num >> 1;

            ++ indexBit;

      }

 

      return indexBit;

}

 

///

// Is the indexBit bit of num 1?

///

bool IsBit1(int num, unsigned int indexBit)

{

      num = num >> indexBit;

 

      return (num & 1);

}

 

网络转载处http://zhedahht.blog.163.com/

两个排序的数组A和B分别含有m和n个数，找到两个排序数组的中位数，要求时间复杂度应为O(log (m+n))。
在线评测地址：
LintCode 领扣​www.lintcode.com
说明
中位数的定义：
这里的中位数等同于数学定义里的中位数。
中位数是排序后数组的中间值。
如果有数组中有n个数且n是奇数，则中位数为A[(n-1)/2]
A[(n−1)/2]。
如果有数组中有n个数且n是偶数，则中位数为 (A[n / 2] + A[n / 2 + 1]) / 2
(A[n/2]+A[n/2+1])/2.
比如：数组A=[1,2,3]的中位数是2，数组A=[1,19]的中位数是10。
样例1
输入:
A = [1,2,3,4,5,6]
B = [2,3,4,5]
输出: 3.5
样例2
输入:
A = [1,2,3]
B = [4,5]
输出: 3
算法：归并
解题思路
最简单的思路是将两个数组合并，然后返回新数组的中位数。九章算法班中讲过，两个有序数组的合并是经典归并排序算法的一步，我们可以新开一个数组，保存合并后的结果。但是我们这样会做额外的工作，因为我们不必保存整个新数组，只需要知道新数组的中位数即可。
因此，更简便的方法是，使用双指针分别对两个数组遍历，比较两个指针下的元素大小，每次移动更小的指针，通过移动次数确定中位数的位置。
算法流程
令指针p1和p2分别指向两个数组，初始指向位置0。我们需要遍历(m + n)/2 + 1次，每次比较两个位置的元素，在第k次比较时，较小的那个值就是两个数组中第k + 1小的数。如果一个指针已经走到了数组末尾，那么移动另一个指针，否则每次将指向较小数的指针后移，直到遍历到中位数。
为了将奇偶情况合并，在代码中用了left和right保存中间值，如果是奇数直接返回right，如果是偶数就返回(left + right) / 2。
复杂度分析
复杂度分析：
时间复杂度：O(m+n)，m和n分别是两个数组的长度。双指针遍历两个数组，指针移动次数是0(m+n)级。
空间复杂度：O(1)。
public class Solution {
    /*
     * @param A: An integer array
     * @param B: An integer array
     * @return: a double whose format is *.5 or *.0
     */
    public double findMedianSortedArrays(int[] A, int[] B) {
        int m = A.length, n = B.length;
        int p1 = 0, p2 = 0;
        int left = -1, right = -1;
        for (int i = 0; i < (m + n) / 2 + 1; i ++){
            left = right;
            // p2 右移
            if (p1 >= A.length || p2 < B.length && A[p1] > B[p2]){
                right = B[p2++];
            }
            // p1 右移
            else {
                right = A[p1++];
            }
        }
        return (m + n) % 2 == 1 ? right : (left + right) / 2.0;
    }
}
二分和快速选择等更多解法见：
九章算法 - 帮助更多中国人找到好工作，硅谷顶尖IT企业工程师实时在线授课为你传授面试技巧​www.jiuzhang.com

转载自：http://ilovers.sinaapp.com/article/快速排序和寻找中位数


寻找中位数
之所以，起“快速排序和寻找中位数”这个题目，并不是因为寻找中位数的时候使用了快速排序，而是这两个算法使用了一个同一个预处理结构 —— 划分，然后都是递归解决！中位数的也是根据一个数把原来的数划分一下，形成两部分。如果前半部分足够长，就在前部分找，否则在后半部分找！(这不仅适合中位数，实际上适合寻找第 k 大的数！！而 select_middle 其实不是来寻找中位数，是在寻找第 nth 大的数，如果 nth == (n+1)/2，这就是中位数！)
select_middle(int *data, int start, int last, int nth); 说明：data 是数据，start 是起始位置，last 是最后一个数据的下一个位置，nth 指定要寻找第 nth 大的数！划分和快速排序是一模一样的，递归那部分也很简单，如果左半部分长就在左半部分找，如果右半部分长，就在右半部分找剩下的小一部分，比如 nth == 10，如果左边个数是 4，那么就在右边找第 6th 大的数！跟快速排序不同的是，递归只需要针对一部分处理！
复杂度分析
blog 还不能到此结束！O__O"…快速排序写起来不容易，插入排序、冒泡儿排序和简单选择排序，都很容易写出来丫，那 me 们为什么要花这么长时间写个快速排序呢？时间复杂度低？低在哪里？还有就是寻找中位数的程序，不，是寻找第 k 大数的程序，那样写有神马好处？它的复杂度能低于 O(nlogn) 吗？！基于划分的求 nth 大的数的那个程序，最坏情况是 O(n^2)，平均是 O(n) ! O__O"…
严格的分析是 me 不喜欢的，但是 me 也不希望太过于“想当然”。先看快速排序 —— 先划分再递归排序。当然有极端情况，有木有！比如 1 2 3 4 5 这样的，每次划分，一部分只有一个数据，另外一部分还是特别多，这样的话，递归要多少次呢？差不多 n 次吧？每递归一次对于数据还很多的那一部分差不多还需要 n 的重新划分吧，那么复杂度上限就是 O(n^2) 有木有！所以快速排序最坏情况的时间复杂度是 O(n^2) 。但是，最坏的情况，要么就是正向有序，要么就是逆向有序，而多数情况，可以想象(就权当是吧)，每次划分，分成差不多相等的两部分，然后每一部分再处理，直到每一部分只有
 1 个元素为止！如果用递推公式描述复杂度，可以用下图的第三个表示：
T(n) = T(n/2)
T(n) = 2T(n/2)
T(n) = 2T(n/2) + n
T(n) = T(n/2) + n
如果最初是 8 个元素，第一次划分，大体是 4+4，第二次划分大体是 2+2，第三次是 1+1，递归深度是 log n 有木有！每次重新划分，就按 n 算，时间复杂度 O(nlogn) ！那 O(nlogn) 是不是选择中位数的那个程序的时间复杂度呢？
前面的四个式子，实际反应了四种情况，虽然看上去都是分治，然后递归解决！第一种情况是个神马情况呢？意思是处理 100 个数据，和处理其中 50 个数据是一样的！处理 50 个和处理其中的 25 个一样的！而这种划分，竟然没有代价，因为后面没有 + 任何东西！这样的话，想象一下，对于所有的 n，问题都可以转化为处理 1 个数据的情况，而且几乎不增加额外开销，那么复杂度就是 O(1) 丫，有木有！再看第三个式子，反映的是，需要 100 个工作量将 100
 化成 50+50 的两部分，每一部分的 50 都要递归求解，所以是 2 倍丫！上面说了，复杂度是 O(nlogn)，如果用式子看：T(8) = 2T(4) + 8 = 4T(2) + 2*4 + 8 = 8T(1) + 4*2 + 2*4 + 8 = 8 + 8 + 8 + 8 + 8 = 4*8，更通用有点：
T(2^n) = 2^n + 2 (2^ n-1) + 4() + 8 () + ... + 2^n = (n+1)2^n，也就是 T(n) = (logn+1)n
上面虽然是近似计算，但是已经能反映问题了。还有就是第二个式子和第四个式子反映的是神马情况？第二个式子反映，划分不需要代价，划分成两部分，两部分工作量再加在一起，O__O"… ！给人感觉，这样的话，T(n) = n ! 有木有！比如 n = 8，T(8) = 2T(4) = 4T(2) = 8 T(1) = 8 ，这貌似是个线性时间！O__O"…
第四个式子反映，需要 n 步将一个工作量为 n 的划分成两部分，后续只需要处理两部分中的一部分！没有 2 倍关系有木有！将递推式子迭代下去：
T(n) = n + n/2 + n/4 + n/8 + ... + 1 = 2n ！O__O"…，
这是神马情况？！线性时间？系数是 2 ？！好吧，也就是说，如果真的能均匀划分的话，上面求中位数的程序的时间复杂度就是 O(n) ! 当然，实际上常量系数要高一些，不会仅仅只有 2 ！
后话
上面的程序和复杂度分析是 me 写的，而主要的算法思想等来自数据结构、算法(算法导论)和程序设计语言(c程序设计语言)。对于程序和复杂度分析，或是 blog 有其他错误的地方，不吝赐教丫，O__O"…对了，编程之美上有一道题，这里作为最后一个补充呈献上来：n 个数中，已知某个数出现的次数多于一半，请找出来这个数！为嘛留这个题了，貌似要找的数，一定是中位数有木有！！当然还有其他解法，而且复杂度可以降到 O(n)，O__O"…