算法不是一蹴而就的，需要扎实的基本功。不仅要懂得算法的基本思想过程，更重要的是能动手实现。本篇博客主要说一些数组算法的小问题。

本篇使用C++,头文件如下 

1
2
3
#include <iostream>
#include <vector>
#include <algorithm>

特殊数组中的查找

题目要求：
一个整数数组中有一个元素出现了一次，其他元素都出现了两次，使用最小的时间复杂度找出出现一次的数
拓展问题：
（1）如果有两个数均出现了一次，其他都出现了两次，如何查找这两个数？
（2）如果一个数组中有一个数出现了一次，其他数都出现了三次，如何找到出现一次的数？

如果没有位操作在算法上应用的思想，这个问题还是蛮难的。废话少说，直接切入主题。
众所周知，两个相同的数异或结果为零，零与任何数异或为其本身。那么这个问题就很好解决了： 

1
2
3
4
5
6
7
8
9
10
int SelectNumber(vector<int>& v)
{
	int res=v[0];
	for (int i = 1; i < v.size(); i++)
	{
		/* 异或运算，相同为0,不同为1 */
		res ^=v[i];
	}
	return res;
}

对于扩展（1），要是能把它变成两个原问题就好了。哈哈，问题就是这么解决的。
第一步：所有的数异或，其实就是那两个不同的数异或的结果
第二步：找这两个数，出现第一位不同的二进制位的位置
第三步：根据这个二进制位将原数组分成两个数组，且这两个数组都满足原题目的要求
第四步：运用原题目的方法找出这两个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void SelectNumber2(vector<int>& v,int& num1,int& num2)
{
	int tmp=0;
	int j;
	for (int i = 0; i < v.size(); i++)
	{
		/* 求出两个数的异或结果 */
		tmp^=v[i];
	}
	//找到两个数第一个不同的位
	for (j = 0; j < sizeof(int)*8; j++)
	{
		if(((tmp>>j)&1)==1)
			break;
	}
	num1=0;
	num2=0;
	//按照第j位不同将数据分成两类（显然所求的两个数不在同一类，而且相同的数还在同一类）
	for (int i = 0; i < v.size(); i++)
	{
		//无论是等于0还是等于1，都不影响分类
		if(((v[i]>>j)&1)==0)
			num1^=v[i];
		else
			num2^=v[i];
	}
}

对于扩展（2）,这个问题很不好解，因为前面的方法不顶用了。不过要是深刻了解到扩展（1）的精髓，那就是利用位操作对数组进行分类，那是可以解决的。还是先来一个例子吧。
数组：2 2 2 3 3 3 4. 首先用第一位（从低到高）来分类(与运算)：
  2         3        5
0010      0011     0101
0001      0001     0001

0000      0001     0001
根据相与的结果，可以把3和5分为①类，2分为另②类。通过类成员的个数是否为3的倍数来判断哪个类是我们需要的，显然这里是①类
然后用第二位对①类来分类，
  3         5
0011      0101
0010      0010

0010      0000
判断结果是否为零，来进行分类（如果第二位无法分类，则用第三位、第四位…..）,通过反复分类，最后所求的数分在一类，且类成员个数为1（就是它本身）
说了这么多，还是上代码吧： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int SelectNumber3(vector<int>& v)
{
	int i,j;
	int low=0,high=v.size()-1;
	int bit =1;
	//通过某一位的值将数组分为两部分，其中一部分包含了待找的数 另一部分不包含
	while(low <= high)
	{
		//由题意必然会收敛到low==high
		if(low == high)
			return v[low];
		i = low-1;
		//把数值分成两类且相同的数必然在同一类，i为分界线.
		for(j = low;j<= high;j++)
		{
			if((v[j]&bit) == 0)
			{
				i++;
				swap(v[i],v[j]);
			}
		}
		//重新得到包含所求元素的数值，显然长度减少了.
		if(i >= low)
		{
			if((i-low+1)%3 == 0)
				low = i+1;
			else
				high =i;
		} 
		bit = bit<<1;
	} 
	//保存编译时不报没有返回值的错，其实用于运行不到这一步.
	return 0;
}

第K大问题

题目要求：在一个整数数组中，查找该数组中第K大的元素。
拓展问题：Top K问题！

这两个问题都是计算机界经典问题。对于原题目，思路是这样的:
第一步：选择一个基准点，进行快排（也就是比它大的放在左边，比它小的放在右边），同时记录比它大的个数count;
第二步：然后比较k与count+1的大小，若k小，则所求的值在左边，接着对左边进行递归，若k大，则所求的值在右边，接着对右边进行递归，若相等，返回该值。

上面的思路很清晰，这里的关键是快排算法如何去实现：
第一步：首先将基准点交换到数组的首位，使其在比较过程中不参与交换
第二步：设立两个指针，一个用于遍历数组，另一个指针m用于指向比基准点大的值应该放的位置
第三步：遍历完数组后，将首位的基准点和最后m指向的值进行交换，这样一次快排就完成了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int Find_k(vector<int>& v,int low,int high,int k)
{
	if(k<=0)
		return -1;
	if(k>high-low+1)
		return -1;
	//随机初始化一个基准点
	int pivot = low+rand()%(high-low+1);
	//记录比基准点大的数的个数。
	int count=0;
	//比基准点大的值应该放的位置
	int m=low;
	//将基准放在数值的最前面。
	swap(v[pivot],v[low]);
	for (int i = low+1; i <= high; ++i)
	{
		if(v[i]>v[low])
		{
			swap(v[++m],v[i]);
			count++;
		}
	}
	//将基准点放到分界点
	//因为m始终指向比基准点大的值或者基准点本身
	swap(v[m],v[low]);
	if(k<(count+1))
		Find_k(v,low,m-1,k);
	else if(k>(count+1))
		Find_k(v,m+1,high,k-(count+1));
	else
		return v[m];
}

对于拓展问题，使用C++ STL模板中已有的数据结构堆和最大堆排序算法 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//查找最小的K个数
void FindMinTopK(vector<int>& vec,int k)
{
	vector<int> heap(vec.begin(),vec.begin()+k);
	make_heap(heap.begin(),heap.end());
	int i;
	//开始处理剩余的数据
	for(i =k;i<vec.size();i++)
	{
		if(vec[i]<heap[0])
		{
			pop_heap(heap.begin(),heap.end());
			heap.pop_back();
			heap.push_back(vec[i]);
			push_heap(heap.begin(),heap.end());
		}
	}