今天学这个东西的时候，看到这种线性的数据结构加上排序步骤，很难不想写个程序来跑跑。

先来说说中位数，这个比较有思路。

中位数

具体的操作步骤应该是：排序 => 获得数据元素个数n => 是奇数 ? (n+1) / 2 : n / 2

那么排序就用之前学的冒泡排序，这种题目大概不会完全倒序给数据，编写sort函数：

1
2
3
4
5
6
7
8
9
10
11
12
void sort(int arr[], int n)
{
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

接下来是判断奇偶，奇偶的判断非常简单，对取模运算的值比对就可以，编写is_even函数，判断奇偶性。

1
2
3
4
5
6
7
8
int is_even(int data)
{
  if (data % 2 == 0) {
    return true;
  } else {
    return false;
  }
}

完成了奇偶判断，下一步就可以正式进行中位数的运算，编写get_median函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
double get_median(int arr[], int length)
{
  // 获取索引
  double result = 0;
  sort(arr, length);
  if (is_even(length)) {
    int median_index_1 = arr[(length / 2) - 1];
    int median_index_2 = arr[length / 2];
    // 计算数据
    result = (median_index_1 + median_index_2) / 2.0;
  } else {
    result = arr[length / 2];
  }

  return result;
}

这个函数首先计算了中位数在数组的哪个索引，然后进行了计算。

众数

众数（Mode）是指在统计分布上具有明显集中趋势点的数值，代表数据的一般水平。 也是一组数据中出现次数最多的数值，有时众数在一组数中有好几个。用M表示。

那么，在程序中，想要计算一个值出现的次数并比对，可拆分为两步。

  1. 计算出每一个数据出现的次数
  2. 结果排序比对
  3. 找出最大值

我没学过什么高级的数据结构，就用这个复制数组的笨办法吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int get_mode(int arr[], int length)
{
  int *copy_arr = malloc(length * sizeof(int));
  memcpy(copy_arr, arr, length * sizeof(int));
  sort(copy_arr, length);

  int max_count = 0;
  int current_count = 1;
  int mode = copy_arr[0];

  for (int i = 1; i < length; i++) {
    if (copy_arr[i] == copy_arr[i - 1]) {
      current_count++;
    } else {
      if (current_count > max_count) {
        max_count = current_count;
        mode = copy_arr[i - 1];
      }
      current_count = 1;
    }
  }

  if (current_count > max_count) {
    mode = copy_arr[length - 1];
  }

  free(copy_arr);
  return mode;
}

这个函数干了以下几件事：

  • 复制数组
  • 排序复制好的数组
  • 对比数组元素，如果array[i] == array[i - 1]，出现次数+1
  • 如果遇到新元素，检查是否需要更新最大值
  • 动态更新众数值

测试跑一把，输出如下

1
2
3
4
5
6
7
int main()
{
  int arr[] = {1, 1, 1, 1, 2, 2, 4, 5, 7, 4, 4, 4, 4, 4, 4, 4, 4, 4, 2};
  int length = sizeof(arr) / sizeof(arr[0]);
  int result = get_mode(arr, length);
  printf("result = %d\n", result);
}
1
result = 4

这个办法实在是有点蠢，找时间仔细学学哈希表，应该能更快。