选取两个有序数组中最大的K个值,降序存入另一个数组中

原题:

假设有两个有序的整型数组int *a1, int *a2,长度分别为m和n.试用C语言写出一个函数选取两个数组中最大的K个值(K可能大于m+n)写到int *a3中,保持a3降序,并返回a3实际的长度。

函数原型为int merge(int *a3, int *a1, int m, int *a2, int n, int k)
解题思路:此题为两个有序数组的合并:
 设置两个下标索引 i和j,逐个比较a1[i]和a2[j],大的进入a3;
 当a1或者a2已经全部被排序,就将另一个数组部分拷贝到a3.
  1. #include <stdio.h>
  2. int merge(int *a3, int *a1, int m, int *a2, int n, int k)
  3. {
  4. int i, j, t;
  5. if(k > m+n)
  6. k = m+n;
  7. for(i = 0, j = 0,  t = 0; t < k; t++)
  8. {
  9. if(i == m) //若a1片段已经全部被排序
  10. {
  11. while(j <= k-m)
  12. a3[t++] = a2[j++];
  13. break;
  14. }
  15. else if(j == n)  //若a2片段已经全部被排序
  16. {
  17. while(i <= k-n)
  18. a3[t++] = a2[i++];
  19. break;
  20. }
  21. if(a1[i] > a2[j])
  22. {
  23. a3[t] = a1[i];
  24. i++;
  25. }
  26. else if(a1[i] <= a2[j])
  27. {
  28. a3[t] = a2[j];
  29. j++;
  30. }
  31. }
  32. return k;
  33. }
  34. int main()
  35. {
  36. int a1[7] = {19,14,13,12,9,6,5};
  37. int a2[9] = {100,56,34,16,10,7,6,3,1};
  38. int a3[20];
  39. int len, k, i;
  40. for(i = 0; i<7; i++)
  41. printf(" %d ", a1[i]);
  42. printf("/n");
  43. for(i = 0; i<9; i++)
  44. printf(" %d ", a2[i]);
  45. printf("/n");
  46. printf("insert k =");
  47. scanf("%d", &k);
  48. len = merge(&a3, &a1, 7, &a2, 9, k);
  49. for(i = 0; i < len; i++)
  50. printf(" %d ", a3[i]);
  51. printf("/n");
  52. printf("len = %d/n", len);
  53. system("pause");
  54. }
上一篇:webstorm无法显示左边文件夹目录的解决方法


下一篇:在IDEA中使用JSP中的out内置对象,out.println()——println红色解决方法