剑指offer之调整数组顺序使奇数位于偶数前面

举报
chenyu 发表于 2021/07/27 01:28:48 2021/07/27
【摘要】 1 问题 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分,比如数组{6、 5 、1、 4、2 、7 、3、8、9}我们调整后变成这样{9、5、1、3、7 、2 、4 、8、6}          2 分析 我们利用partiti...

1 问题

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分,比如数组{6、 5 、1、 4、2 、7 、3、8、9}我们调整后变成这样{9、5、1、3、7 、2 、4 、8、6}   

 

 

 

2 分析

我们利用partition算法博客可以知道,这里还是利用两个指针,一个指针指向开始,一个指针指向尾巴,分别从两边进行扫描,我们先从尾巴指针向左移动,发现了奇数就暂停这里,然后开始移动首指针,如果发现是偶数了就保存当前指针,然后和之前扫描到奇数位置进行换位置,终止条件是首指针的值等于尾指针的值。

 

 

 

 

3 代码实现


  
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. void swap(int* a, int* b)
  5. {
  6. int temp = *a;
  7. *a = *b;
  8. *b = temp;
  9. }
  10. void printVector(vector<int> v)
  11. {
  12. for (int i = 0; i < v.size(); ++i)
  13. {
  14. std::cout << v[i] << "\t";
  15. }
  16. std::cout << std::endl;
  17. }
  18. /*
  19. *奇数在偶数前面的函数
  20. */
  21. void reorderOddEven(vector<int>& vector)
  22. {
  23. if (vector.size() <= 0)
  24. {
  25. std::cout << "vector.size is <= 0" << std::endl;
  26. return;
  27. }
  28. int start = 0;
  29. int end = vector.size() - 1;
  30. while (start < end)
  31. {
  32. while (start < end && (vector[end] % 2) == 0)
  33. {
  34. --end;
  35. }
  36. while (start < end && (vector[start] % 2) != 0)
  37. {
  38. ++start;
  39. }
  40. swap(vector[start], vector[end]);
  41. }
  42. }
  43. int main()
  44. {
  45. vector<int> v2;
  46. v2.push_back(6);
  47. v2.push_back(5);
  48. v2.push_back(1);
  49. v2.push_back(4);
  50. v2.push_back(2);
  51. v2.push_back(7);
  52. v2.push_back(3);
  53. v2.push_back(8);
  54. v2.push_back(9);
  55. vector<int> v3;
  56. printVector(v2);
  57. reorderOddEven(v2);
  58. printVector(v2);
  59. return 0;
  60. }

 

 

 

 

4 运行结果


  
  1. 6 5 1 4 2 7 3 8 9
  2. 9 5 1 3 7 2 4 8 6

 

 

 

 

5 优化

比如我们还有类似的问题,比如数组里面有负数和整数,我们要求负数在正数前面,我么知道reorderOddEven函数里面只要把(vector[start] % 2) != 0这个条件进行修改就行,这里我么可以使用函数指针,根据不同的需求传递不同的函数指针下来,达到效果,增加部分代码实现如下。


  
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. void swap(int* a, int* b)
  5. {
  6. int temp = *a;
  7. *a = *b;
  8. *b = temp;
  9. }
  10. void printVector(vector<int> v)
  11. {
  12. for (int i = 0; i < v.size(); ++i)
  13. {
  14. std::cout << v[i] << "\t";
  15. }
  16. std::cout << std::endl;
  17. }
  18. bool isOddEvenNumber(int number)
  19. {
  20. return ((number & 0x1) == 0);
  21. }
  22. bool isNagetiveNumber(int number)
  23. {
  24. if (number > 0)
  25. return true;
  26. else
  27. return false;
  28. }
  29. void reorderOddEvenOne(vector<int>& vector, bool (*func)(int))
  30. {
  31. if (vector.size() <= 0)
  32. {
  33. std::cout << "vector.size is <= 0" << std::endl;
  34. return;
  35. }
  36. int start = 0;
  37. int end = vector.size() - 1;
  38. while (start < end)
  39. {
  40. while (start < end && (*func)(vector[end]))
  41. {
  42. --end;
  43. }
  44. while (start < end && !(*func)(vector[start]))
  45. {
  46. ++start;
  47. }
  48. swap(vector[start], vector[end]);
  49. }
  50. }
  51. int main()
  52. {
  53. vector<int> v2;
  54. v2.push_back(6);
  55. v2.push_back(5);
  56. v2.push_back(1);
  57. v2.push_back(4);
  58. v2.push_back(2);
  59. v2.push_back(7);
  60. v2.push_back(3);
  61. v2.push_back(8);
  62. v2.push_back(9);
  63. vector<int> v3;
  64. printVector(v2);
  65. reorderOddEvenOne(v2, isOddEvenNumber);
  66. printVector(v2);
  67. return 0;
  68. }

运行结果如下


  
  1. 6 5 1 4 2 7 3 8 9
  2. 9 5 1 3 7 2 4 8 6

如果我们要实现负数在前面的数组,我们只需要调用reorderOddEvenOne函数传递isNagetiveNumber作为函数指针就行。

文章来源: chenyu.blog.csdn.net,作者:chen.yu,版权归原作者所有,如需转载,请联系作者。

原文链接:chenyu.blog.csdn.net/article/details/102653823

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。