王若风的技术博客

世界尽头の冷酷仙境

0%

常见算法之数组

发表于 更新于 分类于 Disqus：
本文字数： 713 阅读时长 ≈ 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
30
31
32
33
34
35
36
37
38
List<int> mergeSortedArrays(List<int> arr1, List<int> arr2) {
  List<int> merged = [];
  int i = 0, j = 0;

  // 比较两个数组中的元素，按顺序放入结果数组
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      merged.add(arr1[i]);
      i++;
    } else {
      merged.add(arr2[j]);
      j++;
    }
  }

  // 如果 arr1 有剩余元素，添加到结果数组
  while (i < arr1.length) {
    merged.add(arr1[i]);
    i++;
  }

  // 如果 arr2 有剩余元素，添加到结果数组
  while (j < arr2.length) {
    merged.add(arr2[j]);
    j++;
  }

  return merged;
}

// 测试代码
void main() {
  List<int> arr1 = [1, 3, 5, 7];
  List<int> arr2 = [2, 4, 6, 8];

  List<int> result = mergeSortedArrays(arr1, arr2);
  print("Merged Sorted Array: $result");
}

求无序数组的中位数

排序法

先将数组排序，然后取中间的元素作为中位数。如果数组长度为奇数，则中位数为中间那个数；如果数组长度为偶数，则中位数为中间两个数的平均值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
double findMedianWithSorting(List<int> nums) {
  nums.sort(); // 对数组进行排序

  int n = nums.length;
  if (n % 2 == 1) {
    // 奇数长度，返回中间元素
    return nums[n ~/ 2].toDouble();
  } else {
    // 偶数长度，返回中间两个元素的平均值
    return (nums[n ~/ 2 - 1] + nums[n ~/ 2]) / 2.0;
  }
}

// 测试代码
void main() {
  List<int> nums = [3, 5, 1, 4, 2];
  print("Median is: ${findMedianWithSorting(nums)}"); // 输出中位数
}

快速选择法（适合大数组）

快速选择法基于快速排序的划分思想。它的思路是利用分治法找到数组的中位数，而不需要对整个数组进行排序。对于长度为奇数的数组，可以找到第 n/2 小的元素；对于长度为偶数的数组，可以找到第 n/2 和第 n/2 - 1 小的元素，并计算平均值。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
double findMedianWithQuickSelect(List<int> nums) {
  int n = nums.length;
  if (n % 2 == 1) {
    // 奇数长度，找到第 n/2 小的元素
    return quickSelect(nums, 0, n - 1, n ~/ 2).toDouble();
  } else {
    // 偶数长度，找到第 n/2 和第 n/2 - 1 小的元素，取平均
    int mid1 = quickSelect(nums, 0, n - 1, n ~/ 2);
    int mid2 = quickSelect(nums, 0, n - 1, n ~/ 2 - 1);
    return (mid1 + mid2) / 2.0;
  }
}

// 快速选择算法的实现
int quickSelect(List<int> nums, int left, int right, int k) {
  if (left == right) return nums[left];

  int pivotIndex = partition(nums, left, right);

  if (k == pivotIndex) {
    return nums[k];
  } else if (k < pivotIndex) {
    return quickSelect(nums, left, pivotIndex - 1, k);
  } else {
    return quickSelect(nums, pivotIndex + 1, right, k);
  }
}

// 分区函数，用于划分数组
int partition(List<int> nums, int left, int right) {
  int pivot = nums[right];
  int i = left;

  for (int j = left; j < right; j++) {
    if (nums[j] <= pivot) {
      int temp = nums[i];
      nums[i] = nums[j];
      nums[j] = temp;
      i++;
    }
  }

  int temp = nums[i];
  nums[i] = nums[right];
  nums[right] = temp;

  return i;
}

// 测试代码
void main() {
  List<int> nums = [3, 5, 1, 4, 2];
  print("Median is: ${findMedianWithQuickSelect(nums)}"); // 输出中位数
}