[剑指Offer]最小的K个数

“岁岁平安”通过精心收集，向本站投稿了8篇[剑指Offer]最小的K个数，以下是小编帮大家整理后的[剑指Offer]最小的K个数，欢迎大家分享。

[剑指Offer]最小的K个数

篇1：[剑指Offer]最小的K个数

题目描述

输入n个整数，找出其中最小的K个数，例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,

直接使用sort排序，然后返回前k个数：

class Solution {public:    vectorGetLeastNumbers_Solution(vectorinput, int k) {  sort(input.begin, input.end());  vectorr;  if(k>input.size()){return r;  }  for(int i=0;i

篇2：最小的k个数

void GetLeastNumbers(int* input, int n, int* output, int k)

{

if (input == NULL || utput == NULL || k > n || n <= 0 || k <= 0)

return;

int start = 0;

int end = n - 1;

int index = Partition(input, n, start, end);

while (index != k - 1)

{

if (index > k - 1)

{

end = index - 1;

index = Partition(input, n, start, end);

}

else

{

start = index + 1;

index = Partition(input, n, start, end);

}

for (int i = 0; i < k; ++i)

output[i] = input[i];

}

typedef multiset> intSet;

typedef multiset>::iterator setIterator;

void GetLeastNumbers(const vector& data, intSet& leastNumbers, int k)

{

leastNumbers.clear();

if (k < 1 || data.size() < k)

return;

vector::const_iterator iter = data.begin();

for (; iter != data.end(); ++iter)

{

if ((leastNumbers.size()) < k)

leastNumbers.insert(*iter);

else

{

setIterator iterGreatest = leastNumbers.begin();

if (*iter < *(leastNumbers.begin()))

{

leastNumbers.erase(iterGreatest);

leastNumbers.insert(*iter);

}

篇3：[剑指Offer]把数组排成最小的数

题目描述

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个，例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

将数字转化为字符串，然后对字符串进行快速排序

class Solution {public:    string PrintMinNumber(vectornumbers) {     string r;     vectorsr;     for(int i=0;i9?numberToString(n/10):)+char(n%10+'0');    }    static bool compare(const string& a, const string& b){     return a+b<=b+a;    } };

篇4：[剑指Offer]二叉搜索树与双向链表

#includeusing std::cout;using std::cin;using std::endl;struct TreeNode {     int val;     struct TreeNode *left;     struct TreeNode *right;     TreeNode(int x) : val(x), left(NULL), right(NULL) {     }};class Solution {public:    TreeNode* Convert(TreeNode* pRootOfTree)    {    TreeNode* p = pRootOfTree;    TreeNode* pl;    TreeNode* pr;    if( p != NULL ) {   pl = Convert(p->left);   pr = Convert(p->right);   p->right= pr;   if(pr){  pr->left = p;   }   while(pl&&pl->right){  pl = pl->right;   }   if(pl)  pl->right= p;   p->left= pl;   while(p->left){  p = p->left;   }    }    return p;    }};int main(){     TreeNode* p1 = new TreeNode(1);     TreeNode* p2 = new TreeNode(2);     TreeNode* p3 = new TreeNode(3);     TreeNode* p4 = new TreeNode(4);     TreeNode* p5 = new TreeNode(5);     TreeNode* p6 = new TreeNode(6);     TreeNode* p7 = new TreeNode(7);     p4->left = p2;     p4->right= p6;     p2->left = p1;     p2->right= p3;     p6->left= p5;     p6->right= p7;     Solution s;     TreeNode* p = s.Convert(p4);     while(p->right){cout<

val<< ;p = p->right;     }     cout<

val<< ;     cout<<;     while(p->left){cout<

val<< ;p = p->left;     }     cout<

val<< ;}

篇5：[剑指Offer]二叉搜索树与双向链表

使用递归，分别去将当前节点的左右子树变成双向链表，然后获取左边链表的最后一个元素，当前元素的左指针指向它，它的右指针指向当前元素；右边链表的第一个元素，它的左指针指向当前元素，当前元素的右指针指向它；然后从当前元素开始，不断从左边找，找到第一个元素，返回此元素的指针。

对这种涉及到二叉树的题目，可以使用测试驱动开始，先写测试用例，然后再编码。

篇6：[剑指Offer]二叉搜索树的后序遍历序列

classSolution {public:    bool VerifySquenceOfBST(vectorsequence) {  if(sequence.size == 0) {return false;  }  returnVerify(sequence);    }    bool Verify(vectorsequence) {  intsize = sequence.size();  if(size <= 1) {return true;  }  //开始切割数列  vectorsmaller;  //第一段，比root小  vectorlarger; //第二段，比root大  //根的值  introot = sequence[size - 1];  //判断此时是否还在第一段，若已经在第二段，但又回到了第一段  //则返回false  bool isOne = false;  //如果第一个数小于root，则表明有第一段，isOne为true  if(sequence[0] < root) {isOne = true;  }  for(inti = 0; i < size - 1; i++) {//比根小if(sequence[i] < root) {    if(isOne == false) {  returnfalse;    }    smaller.push_back(sequence[i]);}//比根大else{    if(isOne)  isOne = false;    larger.push_back(sequence[i]);}  }  returnVerify(smaller) && Verify(larger);    }};

总结：

应该多弄点测试用例，自己测试完后，再提交