数组篇

2.1 求最小的k个数：

题目描述：有n个整数，请找出其中最小的k个数，要求时间复杂度尽可能低。

解法一：

思路：快排后输出前k个元素，O(nlogn).

writer: zzq

function: 给定一个数组，寻找数组中最小的k个数。

方法一：先对数组进行排序（快排）, 然后选择前k个数。

快排思想： 分治＋挖坑

挖坑：

1) 先找到一个基准值a[i]，存到key里面，然后把a[i]挖空；

2) 从j开始往前找（j--）,找到第一个比key小的数，就用当前的a[j]来填补之前的a[i]，把a[j]挖空；

3) 从i开始往后找（i++），找到第一个比key大的数，就用当前的a[i]来填补上面的a[i],再把a[i]挖空；

4) 如此循环，直到i==j;

5）然后把key中的值存到a[i]中。【此时，key前面的数都比key小，key后面的数都比key大】e.g.--------------,key,-----------------

分治：

以基准值key所在的位置作为划分点，

quicksort(*a,left,i-1) ;

quicksort(*a,i+1,right);

时间复杂度：排序O(nlogn) + 输出前k个元素O(k), k远小于n时，复杂度为O(nlogn)



#include<iostream>

#include<algorithm>

#include<string>

#include<stdio.h>

using namespace std;

void QuickSort(int *a, int start, int end){

	if(start<end){

		//***************挖坑********************//

		int i = start;

		int j = end;

		int key = *(a+start);  // 用key来存中间阈值

	//	cout<<key<<endl;

		while(i<j){

			while(i<j&&*(a+j)>key)j--;// 从后往前找比key小的第一个元素

			if(i<j){

				*(a+i)=*(a+j);

				i++;//  为什么只给i++,j的值不变呢，因为要记录当前的挖坑位置，下一次借助这个索引值来填坑。

			}

			while(i<j&&*(a+i)<key)i++;

			if(i<j){

				*(a+j)=*(a+i);

				j--;

			}

		}

		*(a+i)=key; // 将key填充到最终的坑中，此时满足key前面的元素逗比key小，key后面的元素都比key大。

		//******************分治*****************//

		QuickSort(a, start, i-1);  // 左半部分

		QuickSort(a, i+1 , end);   // 右半部分

	}

}

int main(){

	int n,k;

	cin>>n>>k;

	int a[n];

    for (int i=0;i<n;i++)cin>>a[i];

    //int a[]= {72,6,57,88,60,42,83,73,48,85};

	QuickSort(a,0,n-1);

	for(int j=0;j<k;j++)cout<<a[j]<<' ';

    return  0;

}

解法二：

思路：局部排序后输出k个元素，O(nk).

writer: zzq

function: 给定一个数组，寻找数组中最小的k个数。

方法二：题目没有要求找到的k个最小数必须有序，也没有要求后面的n-k个数有序。

所以不必对整个数组进行排序，只需要对k个数部分排序即可。

1）顺序遍历数组a的前k个元素，保存在数组minK中；

2）选择排序|快速排序找出最大值kmax;

3）顺序遍历后面的n-k个数，如果比kmax大，则index++；否则用当前a[index]代替kmax，并重新对数组minK排序;

4）那么minK中保存的即为最小的k个数。

时间复杂度：(n-k)O(k)+O(k), k远小于n时, O(nk)

【找minK中的最大值需要遍历k个元素：O(k);

每次更新or not；O(k)|0,共有n-k个待遍历元素，所以为(n-k)O(k);

输出minK中的k个数：O(k)。

】

#include<iostream>

#include<algorithm>

#include<stdio.h>

using namespace std;

void GetMaxK(int *a,int length, int* KM){

	int maxK=*a;

	int index = 0;

	for(int i=1;i<length;i++){

		if(maxK<*(a+i)){

			maxK=*(a+i);

			index=i;

		}

	}

	*KM=maxK;

	*(KM+1)=index;

}

int main(){

	int n,k;

	int KM[2];

	cin>>n>>k;

	int a[n],minK[k];

	for(int i=0;i<n;i++){

		cin>>a[i];

		if(i<k)minK[i]=a[i];

	}

	GetMaxK(minK,k,KM);

	for(int i=k;i<n;i++){

		if(*KM>a[i]){ // a[i]比maxK小，替换该元素，重新求maxK

			minK[*(KM+1)]=a[i];

			GetMaxK(minK,k,KM);

		}

	}

	for(int j=0;j<k;j++){

		if(j+1==k)

			cout<<minK[j]<<endl;

		else

			cout<<minK[j]<<' ';

	}

    return  0;

}

解法三：

思路：构建前k个数的大顶堆，每次跟新推后输出k个元素，O(nlogk).

writer: zzq

function: 给定一个数组，寻找数组中最小的k个数。

方法三：利用堆代替数组。

1）用容量为k的最大堆minHk存储最先遍历到的k个数。建堆时间O(k)，建好堆后，堆中元素有序，设minH1<minH2<···<minHk;

2）遍历剩余的n-k个元素，与堆顶元素hk比较，如果当前a[index]>minHk，则不做操作，否则用a[index]替换minHk,然后更新堆,

更新堆的时间为O(logk)

3）输出堆中元素即为所求。

时间复杂度：(n-k)O(logk)+O(k), k远小于n时, O(nlogk)

【建堆：O(k);

更新堆：O(logk);[类似方法二，这是用堆代替数组以后，每次更新堆时间复杂度降低，因为堆是局部有序的]

每次更新or not；O(logk)|0,共有n-k个待遍历元素，所以为(n-k)O(logk);

输出minK中的k个数：O(k)。】

   堆： 特殊的二叉树。

    堆是具有以下性质的完全二叉树：

            每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；

	    或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

    用数组实现，则结构描述为：

        小顶堆：a[i]<=a[2*i+1]&&a[i]<=a[2*i+2];

        大顶堆：a[i]>=a[2*i+1]&&a[i]>=a[2*i+2];



#include<iostream>

#include<algorithm>

using namespace std;

const int MaxN = 100010;

int B[MaxN];

void HeapRefresh(int *a, int index,int length){

      int i = index;

      int child = 2*i+1;

      // 使当前子树满足最小堆

      while(child<length){

        if(child<(length-1)&&*(a+child+1)>*(a+child))  // 右子节点存在，选择较小的子节点

            child++;

        if(*(a+child)>*(a+i)){

            swap(*(a+child), *(a+i));

        }

        else{

            break;

        }

        i = child;

	child = 2*i+1;

      }

} 

void CreatHeap(int *a, int length){

        int j;

        // length/2-1 为最后一个非叶节点

        for(j = length/2-1;j>=0;j--){

            HeapRefresh(a, j,length);

        }

}

int main(){

	int n,k;

	cin>>n>>k;

	int minH[k];

	for(int i=0;i<n;i++){

                cin>>B[i];

		if(i<k)minH[i]=B[i];

	}

	CreatHeap(minH,k);

	for(int i=k;i<n;i++){

		if(B[i]<minH[0]){

			minH[0]=B[i];

			HeapRefresh(minH,0,k);

		}

	}

	for(int j=0;j<k;j++){

		if(j+1==k)

			cout<<minH[j]<<endl;

		else

			cout<<minH[j]<<' ';

	}

	return 0;

}

解法四：

思路：线性选择算法，O(n).

（未完待续）

巴特西

编程之法section II: 2.1 求最小的k个数

数组篇