CWYAlpha

Just another WordPress.com site

Thought this was cool: 查找最小的k个元素

leave a comment »


给定一个数组和一个k,输出最小的k个数字。

这个问题有多重解法,譬如:
1、sort, top K,时间复杂度O(nlogn)
2、小顶堆排序,pop+调整k次,时间复杂度O(n+klogn)。
3、选择排序,每次选min,swap到头部时间复杂度O(nk)。

这里写下选择排序这个。

#include <stdio.h>

void select_min(int* arr, int n, int k)
{
	int i, j, tmp;
	int min,minP;
	for(i=0; i<k; i++)	
	{
		min = arr[i];
		minP = i;
		for(j=i+1; j<n; j++)
		{
			if(arr[j]<arr[minP])	
			{
				minP = j;
				min = arr[j];
			}
		}
		if(minP!=i)
		{
			tmp = arr[minP];
			arr[minP] = arr[i];
			arr[i] = tmp;
		}
	}
	// Print min k
	for(i=0;i<k;i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

int main()
{
	int arr[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, -1};
	int k = 3;
	select_min(arr, sizeof(arr)/sizeof(int), 3);
	return 0;
}

from 四号程序员四号程序员: http://www.coder4.com/archives/3248

Written by cwyalpha

五月 31, 2012 在 4:09 下午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: