個(gè)人中心
退出
劍指offer之最小的K個(gè)數(shù)
1 問(wèn)題
輸入N個(gè)整數(shù)，找出其中最小的K個(gè)，例如輸入數(shù)組6、5、1、4、 2、 7、 3、 8，最小的4個(gè)數(shù)是1、2、3、4
2 分析
1）我們可以用快速排序從小到大，但是時(shí)間復(fù)雜度是O(nlogn) 我們?nèi)〕鲎钋懊娴腒個(gè)數(shù)就行。
2）用partition算法，時(shí)間復(fù)雜度是O(n)
我之前的博客講解partition算法的總結(jié)如下：
我們使用partition算法的時(shí)候，從我們上面代碼第一次調(diào)用來(lái)看，我們選擇的第一個(gè)數(shù)字5作為中間軸，然后執(zhí)行一次后，我們的 partition函數(shù)返回的start或者i值都是4，然后我們最后一步把5也插入了vector[4]那里，就是說(shuō)明我們左邊有4個(gè)值比當(dāng)前數(shù)字5作為中間軸都小，也能說(shuō)明這左邊的4個(gè)值和中間軸數(shù)5都是數(shù)組里面最小的5個(gè)值，如果我們需要求出一個(gè)數(shù)組里面最小的5個(gè)值，我們只需要partition算法返回值是4就行，然后在左邊的數(shù)組的前5個(gè)數(shù)字就是這個(gè)數(shù)組里面最小的5個(gè)數(shù)，所以這里的數(shù)組里面最小的多少K個(gè)數(shù)確保partition返回的index或者start的關(guān)系是：index = K - 1; 或者start = K -1關(guān)系，也就是說(shuō)partition函數(shù)返回index或者start值的時(shí)候，數(shù)組里面從坐標(biāo)0到index或者start的值就是數(shù)組里面最小的元素，也就是index+1個(gè)元素。
簡(jiǎn)言之：也就是說(shuō)我們只需要確保partition算法這里返回值是3就行，然后我們?cè)偃?shù)組前面的4個(gè)數(shù)字就是我們需要得到的結(jié)果
優(yōu)點(diǎn)：這里時(shí)間復(fù)雜度為O(n)。
缺點(diǎn)：修改了數(shù)組的數(shù)據(jù)，然后適合數(shù)組數(shù)據(jù)量比較小。
3） 我們單獨(dú)可以一個(gè)空間（這里用mulitSet 配上greater 就可以使得數(shù)據(jù)可以按照從大到小排序，而且中間數(shù)據(jù)的插入，刪除，查找的時(shí)間復(fù)雜度可以保持在O(logk) )保存K個(gè)數(shù)，然后遍歷所有數(shù)據(jù)，如果這個(gè)數(shù)據(jù)小于空間K個(gè)數(shù)的最大值，我們把空間最大值踢出來(lái)，把這個(gè)數(shù)添加到空間里面去
優(yōu)點(diǎn)：適合海量數(shù)據(jù)，因?yàn)橐淮涡詻](méi)有那么大空間裝那么多數(shù)據(jù)，我么可以借助輔助空間。
3 代碼實(shí)現(xiàn)
這里的partitionOne函數(shù)和partitionTwo函數(shù)和partitionTreee函數(shù)效果一樣，我們用其中的一個(gè)就行了。
#include <iostream>
#include <vector>
using namespace std;
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void printVector(vector<int> v)
{
for (int i = 0; i < v.size(); ++i)
{
std::cout << v[i] << "\t";
}
std::cout << std::endl;
}
/*
*partition算法 記得如果這里是C++我們傳遞的是vector類(lèi)型，我們記得要加引用，
*不然改變不了數(shù)據(jù)，這里和java傳遞ArrayList不一樣，ArrayList作為參數(shù)可以改變集合里面的值，
*所以C++如果函數(shù)傳遞非基本數(shù)據(jù)類(lèi)型，一半都是帶引用的
*/
int partitionOne(vector<int>& vector, int start, int end)
{
if (start > end)
{
std::cout << "vector is empty or start > end" << std::endl;
return -1;
}
int pivot = vector[start];
while (start < end)
{
//我們先從尾巴開(kāi)始
while (start < end && pivot <= vector[end])
{
--end;
}
//這里用的數(shù)組賦值，而不是直接用swap交換函數(shù)，那么下面的2步也是用數(shù)組賦值，而不是用swap交換函數(shù)
vector[start] = vector[end];
while (start < end && pivot >= vector[start])
{
++start;
}
vector[end] = vector[start];
}
//std:cout << "start is " << start << "end is " << end << std::endl;
vector[start] = pivot;
//printVector(vector);
return start;
}
/*
*partition算法, 這里只不過(guò)增加了2個(gè)變量i和j
*，
*/
int partitionTwo(vector<int>& vector, int start, int end)
{
if (start > end)
{
return -1;
}
int i = start;
int j = end;
int pivot = vector[start];
while (i < j)
{
//我們先從尾巴開(kāi)始
while (i < j && pivot <= vector[j])
{
--j;
}
//這里用的數(shù)組賦值，而不是直接用swap交換函數(shù)，那么下面的2步也是用數(shù)組賦值，而不是用swap交換函數(shù)
vector[i] = vector[j];
while (i < j && pivot >= vector[i])
{
++i;
}
vector[j] = vector[i];
}
vector[i] = pivot;
//printVector(vector);
// quickSort1(vector, start, i - 1);/*最后用同樣的方式對(duì)分出來(lái)的左邊的小組進(jìn)行同上的做法*/
// quickSort1(vector, i + 1, end);
return i;
}
/*
*partition算法, 這里只不過(guò)增加了2個(gè)變量i和j,然后使用了交換函數(shù)swap
*，
*/
int partitionThree(vector<int>& vector, int start, int end)
{
if (start > end)
{
return -1;
}
int i = start;
int j = end;
int pivot = vector[start];
while (i < j)
{
//我們先從尾巴開(kāi)始
while (i < j && pivot <= vector[j])
{
--j;
}
while (i < j && pivot >= vector[i])
{
++i;
}
//這里用的shiswap交換函數(shù)，那么下面的是是也是swap交換函數(shù)
swap(vector[i], vector[j]);
}
swap(vector[i], vector[start]);
//printVector(vector);
return i;
}
/**
*快速排序 調(diào)用第一個(gè)partitionOne
*/
void quickSortOne(vector<int>& vector, int start, int end)
{
if (vector.size() < 0 || start > end)
return;
int index = partitionOne(vector, start, end);
quickSortOne(vector, start, index - 1);
quickSortOne(vector, index + 1, end);
}
/**
*快速排序 調(diào)用第二個(gè)partitionTwo
*/
void quickSortTwo(vector<int>& vector, int start, int end)
{
if (vector.size() < 0 || start > end)
return;
int index = partitionTwo(vector, start, end);
quickSortTwo(vector, start, index - 1);
quickSortTwo(vector, index + 1, end);
}
/**
*快速排序 調(diào)用第三個(gè)partitionThree
*/
void quickSortThree(vector<int>& vector, int start, int end)
{
if (vector.size() < 0 || start > end)
return;
int index = partitionThree(vector, start, end);
quickSortThree(vector, start, index - 1);
quickSortThree(vector, index + 1, end);
}
/**
* 得到數(shù)組里面最小的幾個(gè)數(shù)
*/
void getLeastNumber(vector<int>& input, int inputLen, vector<int>& output, int k)
{
if (input.size() <= 0 || inputLen <= 0 || k > inputLen || k <= 0)
{
std::cout << "input size is zero or inputLen <=0 or k > inputLen or k<= 0" << std::endl;
return;
}
int start = 0;
int end = inputLen - 1;
int index = partitionTwo(input, start, end);
while (index != k - 1)
{
if (index < k - 1)
{
start = index + 1;
index = partitionTwo(input, start, end);
}
else
{
end = index - 1;
index = partitionTwo(input, start, end);
}
}
for (int i = 0; i < k; ++i)
{
output.push_back(input[i]);
}
}
int main()
{
vector<int> v2;
v2.push_back(6);
v2.push_back(5);
v2.push_back(1);
v2.push_back(4);
v2.push_back(2);
v2.push_back(7);
v2.push_back(3);
v2.push_back(8);
vector<int> v3;
getLeastNumber(v2, v2.size(), v3, 4);
printVector(v3);
return 0;
}
4 運(yùn)行結(jié)果
2 1 3 4
5 借助輔助空間的賽選海量數(shù)據(jù)代碼實(shí)現(xiàn)
#include <iostream>
#include <vector>
#include <set>
#include <functional>
using namespace std;
//typedef multiset<int, greater<int> > intSet; 這樣寫(xiě)錯(cuò)了，中間還要一個(gè)空格
typedef multiset<int, greater<int> > intSet;
typedef multiset<int, greater<int> >::iterator setIterator;
void printSet(intSet set)
{
setIterator iter = set.begin();
std::cout << "----" << std::endl;
for (; iter != set.end(); ++iter)
{
std::cout << "value is " << *iter << endl;
}
std::cout << "----" << std::endl;
}
/**
* 得到數(shù)組里面最小的幾個(gè)數(shù)
*/
void getLeastNumberOne(vector<int>& input, int inputLen, intSet& output, int k)
{
if (input.size() <= 0 || inputLen <= 0 || k > inputLen || k <= 0)
{
std::cout << "input size is zero or inputLen <=0 or k > inputLen or k<= 0" << std::endl;
return;
}
for (vector<int>::iterator iter = input.begin(); iter != input.end(); ++iter)
{
if (output.size() < k)
{
output.insert(*iter);
}
else
{
setIterator setIter = output.begin();
if (*iter < *setIter)
{
//output.erase(*setIter)錯(cuò)錯(cuò)了
//erase函數(shù)不是刪除的指針值，是刪除的指針
output.erase(setIter);
output.insert(*iter);
}
}
}
}
int main()
{
vector<int> v2;
v2.push_back(6);
v2.push_back(5);
v2.push_back(1);
v2.push_back(4);
v2.push_back(2);
v2.push_back(7);
v2.push_back(3);
v2.push_back(8);
intSet v3;
getLeastNumberOne(v2, v2.size(), v3, 4);
setIterator iter = v3.begin();
for (; iter != v3.end(); ++iter)
{
std::cout << "value is " << *iter << endl;
}
return 0;
}
6 運(yùn)行結(jié)果
value is 4
value is 3
value is 2
value is 1
7 總結(jié)
如果看到了什么海量數(shù)據(jù)的話，我么可以單獨(dú)借助輔助空間，然后輔助空間里面以以時(shí)間復(fù)雜度最小來(lái)進(jìn)行刪除、增加、查找操作。
作者：chen.yu
深信服三年半工作經(jīng)驗(yàn)，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號(hào)：編程入門(mén)到禿頭 或掃描下面二維碼
零基礎(chǔ)入門(mén)進(jìn)階人工智能(鏈接)
分類(lèi)導(dǎo)航