2014
04-16

# 九度-1371-最小的K个数

8 4
4 5 1 6 2 7 3 8

1 2 3 4

#include<stdio.h>
#include<algorithm>
using namespace std;
int partition(int arr[], int s, int e){
int x = arr[s];
int r = e+1;
int l = s;
while(l < r){
while(l<e && arr[++l] <= x);
while(r>s && arr[--r] > x);
if(l >= r) break;
swap(arr[r],  arr[l]);
}
arr[s] = arr[r];
arr[r] = x;
return r;
}
int k;
void minK(int arr[],int start,int end){
if(start >= end) return;
int index = partition(arr,start,end);
if(index == k) return;
//类似二分的思想，比快速排序要少一个递归
if(index > k) minK(arr,start,index-1);
else minK(arr,index+1,end);
}
const int M = 200001;
int n,arr[M];
int main()
{
while(scanf("%d%d",&n, &k) != EOF){
for(int i=0; i<n; i++){
scanf("%d", &arr[i]);
}
--k;
minK(arr,0,n-1);
sort(arr,arr+k+1);//输出结果需要是排序的
for(int i=0; i<k; i++)
printf("%d ",arr[i]);
printf("%d\n",arr[k]);
}
return 0;
}

/**************************************************************
Problem: 1371
User: coder
Language: C++
Result: Accepted
Time:810 ms
Memory:1800 kb
****************************************************************/

#include <algorithm>
#include <cstdio>
using namespace std;
int n,k,a[200000];
int l = idx*2 + 1;
int r = idx*2 + 2;
int largeIndex = idx;
//先检查边界。k即为要创建的堆的大小
while( l<k  || r<k ){
if(l<k && a[l] > a[largeIndex]) largeIndex = l;
if(r<k && a[r] > a[largeIndex]) largeIndex = r;
if(largeIndex != idx){
//交换 root和子节点。
swap(a[idx], a[largeIndex]);
//交换之后继续调整子节点
idx = largeIndex;
l = idx*2 + 1;
r = idx*2 + 2;
}else{
break; //无需调整
}
}
}
void buildHeap(){
for(int i= (k-1)/2; i>=0; i--){
}
}
int main(){
while(scanf("%d%d", &n, &k) != EOF){
for(int i = 0; i < k; i++)
scanf("%d", &a[i]);
buildHeap();
for(int i = k; i < n; i++){
scanf("%d", &a[i]);
if(a[0] > a[i]){
swap(a[0],a[i]);
}
}
sort(a,a+k);
for(int i = 0; i<k-1; i++)
printf("%d ", a[i]);
printf("%d\n", a[k-1]);
}
}

/**************************************************************
Problem: 1371
User: coder
Language: C++
Result: Accepted
Time:910 ms
Memory:1800 kb
****************************************************************/

1. 当过城管的表示…兄台遇到的那些是哪里来的山贼啊…我们这边的确是没收东西，但是都要拍照登记签字，然后来写保证书了之后东西都领回去的…有些时候遇到大学生打工在路边摆摊我们都是劝离的，如果多次不听悔改就要确认学生证没收东西然后联系学校方之后让他们来

2. 当过城管的表示…兄台遇到的那些是哪里来的山贼啊…我们这边的确是没收东西，但是都要拍照登记签字，然后来写保证书了之后东西都领回去的…有些时候遇到大学生打工在路边摆摊我们都是劝离的，如果多次不听悔改就要确认学生证没收东西然后联系学校方之后让他们来

3. 当过城管的表示…兄台遇到的那些是哪里来的山贼啊…我们这边的确是没收东西，但是都要拍照登记签字，然后来写保证书了之后东西都领回去的…有些时候遇到大学生打工在路边摆摊我们都是劝离的，如果多次不听悔改就要确认学生证没收东西然后联系学校方之后让他们来

4. 当过城管的表示…兄台遇到的那些是哪里来的山贼啊…我们这边的确是没收东西，但是都要拍照登记签字，然后来写保证书了之后东西都领回去的…有些时候遇到大学生打工在路边摆摊我们都是劝离的，如果多次不听悔改就要确认学生证没收东西然后联系学校方之后让他们来

5. 当过城管的表示…兄台遇到的那些是哪里来的山贼啊…我们这边的确是没收东西，但是都要拍照登记签字，然后来写保证书了之后东西都领回去的…有些时候遇到大学生打工在路边摆摊我们都是劝离的，如果多次不听悔改就要确认学生证没收东西然后联系学校方之后让他们来

6. 因为是要把从字符串s的start位到当前位在hash中重置，修改提交后能accept，但是不修改居然也能accept

7. 不考虑最后将结果排序的话，快排的时间复杂度是O(N) ，而堆排的是O(N*logK),这样比较看，快排快