- 技术博客
- 第k大的元素
堆排序，创建一个大小为k的小顶堆
int findKthLargest(vector
<int>& nums
, int k
) {
vector
<int> mat(k
);
for(int i
=0;i
<k
;i
++)
mat
[i
]=nums
[i
];
for(int i
=k
/2-1;i
>=0;i
--)
adjust(mat
,i
,k
);
for(int i
=k
;i
<nums
.size();i
++)
{
if(nums
[i
]>mat
[0])
{
mat
[0]=nums
[i
];
adjust(mat
,0,k
);
}
}
return mat
[0];
}
void adjust(vector
<int> &a
,int m
,int t
)
{
for(int k
=2*m
+1;k
<t
;k
=2*k
+1)
{
if(k
+1<t
&&a
[k
+1]<a
[k
])
k
++;
if(a
[k
]<a
[m
])
{
swap(a
[k
],a
[m
]);
m
=k
;
}
else
break;
}
}
void swap(int &a
,int &b
)
{
int c
=a
;
a
=b
;
b
=c
;
}
快速排序，右边有k个较大的元素
int findKth(vector
<int> &a
, int n
, int K
)
{
return quick(a
, 0, n
- 1, n
-K
);
}
int quick(vector
<int>& a
, int l
, int r
, int K
)
{
int temp
= a
[l
];
int left
= l
; int right
= r
;
while (l
< r
)
{
while (l
<r
&&a
[r
]>temp
)
r
--;
if (l
< r
)
a
[l
++] = a
[r
];
while (l
< r
&&a
[l
] < temp
)
l
++;
if (l
< r
)
a
[r
--] = a
[l
];
}
a
[l
] = temp
;
if (l
== K
) return temp
;
else if (l
> K
)
return quick(a
, left
, l
- 1, K
);
else
return quick(a
, l
+ 1, right
, K
);
}
