算法面试真题5:无序数组找出中位数(爱奇艺)

题目:给一个无序数组arr和数组长度n,找出其中的中位数。

首先这个题目有个不确定的点,就是如果数组长度n是偶数,那么到底哪个才是中位数?这个应该找面试官问一下,一般会告诉你数组长度n是奇数。

解法1:

很简单,对数组排序,然后输出中间的数arr[(n -1)/2]即可。

排序算法有很多种,如冒泡排序,插入排序,快速排序,堆排序。这里我们讲一下快速排序吧

快速排序

快速排序的意思就是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
一般的步骤是:

  1. 设置两个变量i、j,排序开始的时候:i=0,j=N-1;
  2. 以第一个数组元素作为关键数据,赋值给key,即key=A[0];
  3. 从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j],将A[j]和A[i]互换;
  4. 从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]互换;
  5. 重复第3、4步,直到i=j;

假如有一个数组:arr = {4 5 6 1 2 3 0}

下标 0 1 2 3 4 5 6
数据 4 5 6 1 2 3 0

按照上面的排序步骤可得:
i = 0,j = 6,key = 4
arr[j] = arr[6] = 0 < key,则arr[i] 和 arr[j]互换,变换的数组如下:

下标 0 1 2 3 4 5 6
数据 0 5 6 1 2 3 4

此时:
i = 0 ,j = 6,key = 4
arr[i] = arr[0] = 0 < key,则 i++; 此时: i = 1,j = 6,key = 4 arr[i] = arr[1] =5 > key,则arr[i]和arr[j]互换,变换的数组如下:

下标 0 1 2 3 4 5 6
数据 0 4 6 1 2 3 5

此时:
i = 1,j = 6,key = 4,i key,则 j--
此时:
i = 1,j = 5,key = 4,i<j
arr[j] = arr[5] = 3 < key,则a[i]和a[j]互换,得:

下标 0 1 2 3 4 5 6
数据 0 3 6 1 2 4 5

此时:
i= 1, j = 5,key = 4
a[i] = a[1] = 3 < key,则 i++; 此时: i= 2, j = 5,key = 4 a[i] = a[2] = 6 > key,则a[i]和a[j]互换,得:

下标 0 1 2 3 4 5 6
数据 0 3 4 1 2 6 5

此时:
i= 2,j = 5,key = 4
arr[j] = arr[5] = 6 > key,则j--;
此时:
i= 2,j = 4,key = 4
arr[j] = arr[4] = 2 < key,则a[i]和a[j]互换,得:

下标 0 1 2 3 4 5 6
数据 0 3 2 1 4 6 5

此时:
i= 2,j = 4,key = 4
arr[i] = arr[2] = 2 < key,则i++;
此时:
i= 3,j = 4,key = 4
a[i] = arr[3] = 1 < key,则 i++;
此时:
i= 4,j = 4,则不能再继续比较了
于是我们得到了第一趟比较终止的下标 index = 4;所以我们数组分为两部分数组,一部分是{0 3 2 1 } 和{6 5}
我们利用上面的步骤再分别为这两个数组进行排序,最终能得到一个排序完成的数组。

top Created with Sketch.