关于算法:4-寻找两个正序数组的中位数LeetCode算法题

办法一、暴力解法
即先将两个有序数组合并为一个有序数组，而后求得此有序数组的中位数。因而算法的外围是归并两个有序数组，能够借鉴归并排序里归并两个有序数组的办法。此法工夫复杂度为 O(m+n)，因为须要遍历两个数组所有元素，空间复杂度为 O(m+n)，因为须要开拓新数组存储这两个数组的所有元素。

#include <stdio.h>
#include <stdlib.h>

double findMedienSortedArr(int *arr1, int arr1Size, int *arr2, int arr2Size)
{

  //merge array
  int size = arr1Size + arr2Size;
  int *arr = (int *)malloc(size * sizeof(int));
  int arr1Index = 0;
  int arr2Index = 0;
  double medien;
  for (int index = 0; index < size; index++) {if (arr1Index < arr1Size && arr2Index < arr2Size)
    {if (arr1[arr1Index] <= arr2[arr2Index])
      {arr[index] = arr1[arr1Index];
        arr1Index++;
      }
      else
      {arr[index] = arr2[arr2Index];
        arr2Index++;
      }
    }
    else if (arr1Index < arr1Size && arr2Index >= arr2Size)
    {arr[index] = arr1[arr1Index];
      arr1Index++;
    }
    else if (arr1Index >= arr1Size && arr2Index < arr2Size)
    {arr[index] = arr2[arr2Index];
      arr2Index++;
    }
  }
  // 打印合并后的数组，测试的代码，能够正文掉
  //for (int j = 0; j < size; j++) {//  printf("%d", arr[j]);
  //}
  
  if (size % 2 == 0)
  {medien = (double)(arr[size / 2 - 1] + arr[size / 2]) / 2;
  }
  else
  {medien = arr[size / 2];
  }
  return medien;
}
int main(void)
{int arr1[] = {2, 4, 5, 7, 9, 29, 67};
  int arr2[] = {3, 6, 8, 9, 10, 13, 18};
  int size1 = sizeof(arr1) / sizeof(*arr1);
  int size2 = sizeof(arr2) / sizeof(*arr2);
  printf("arr length: %d %d\n", size1, size2);
  double medien = findMedienSortedArr(arr1, size1, arr2, size2);
  printf("\n");
  for (int i = 0; i < size1; i++)
  {printf("%d", arr1[i]);
  }
  printf("\n");
  for (int j = 0; j < size2; j++)
  {printf("%d", arr2[j]);
  }
  printf("\n");
  printf("medien is %f", medien);
  printf("\n");
}