算法与数据结构（1.4）：divide and conquer 分治法 (six questions, c++)

程序员文章站 2022-06-03 16:52:08

...

分治法一直以来是算法中的经典，难度介于贪心和动态规划之间，本次就来分享一下分治法中非常有代表性的六道题。

Q1: Binary Search

算法与数据结构（1.4）：divide and conquer 分治法 (six questions, c++)

二分查找应该是分治法应用中最基本的算法了，相对于普通查找时间复杂度 O(n) 来说，二分查找的时间复杂度为 O(logn) ，这大大提升了查找的效率。

#include <iostream>
#include <cassert>
#include <vector>

using namespace std;

int binary_search(const vector<int> &a, int x) {
  int low = 0, high = (int)a.size(); 
  int mid;
  while(low <= high){
    mid = (low + high) / 2;
    if(x == a[mid]) return mid;
    else if(x < a[mid]) high = mid - 1;
    else low = mid + 1;
  }
  return -1;
}

int linear_search(const vector<int> &a, int x) {
  for (size_t i = 0; i < a.size(); ++i) {
    if (a[i] == x) return i;
  }
  return -1;
}

int main() {
  int n;
  std::cin >> n;
  vector<int> a(n);
  for (size_t i = 0; i < a.size(); i++) {
    std::cin >> a[i];
  }
  int m;
  std::cin >> m;
  vector<int> b(m);
  for (int i = 0; i < m; ++i) {
    std::cin >> b[i];
  }
  for (int i = 0; i < m; ++i) {
    std::cout << binary_search(a, b[i]) << ' ';
  }
}

以上就是线性查找和二分查找的基本步骤，还是比较简单的。

二分查找的基本思路就是：首先我们对要查找的数组排序，然后不断比较中间元素与查找值得大小来判断查找的指针该向哪边移动：

如果中间值小于查找值，那就只需要搜索右半区；

如果中间值大于查找值，那就只需要搜索左半区；

这样不断迭代，最后找到想找的那个元素。

Q2： Majority Elements

主要元素这个问题说的是我们要从n个元素中找到一个元素，它出现的次数超过一半，如果找不到那就输出0。

只要会写程序语言，应该能想出尚若我们统计每个元素出现的次数，统计出出现次数大于n/2的，便解决了这个问题。但是复杂度为O(n^2)，我们能不能想出一种更快的方法呢？

答案就是使用分治法：

我们将一个数组分为左右半区，如果一个元素是整个数组的主要元素，那么它一定也是左半区或者右半区的主要元素，不然个数不可能超过n/2。假设我们已经得到了左右半区的主要元素（如果哪个半区没有主要元素，则返回值为-1），下面就是如何合并。我们将左右半区合起来，数出左半区主要元素或者右半区主要元素出现的次数是否超过这整个区的一半，谁超过就返回谁。如果都没有超过，就返回-1。

最后输出是判断有无主要元素。

下面是代码：

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int get_majority_element(vector<int> &a, int left, int right) {
  if (left == right) return -1;
  if (left + 1 == right) return a[left];
  //write your code here
  int mid = (left + right) / 2;
  int low = get_majority_element(a, left, mid);
  int high = get_majority_element(a, mid, right);
  int m = 0, n = 0;
  for(int i = left; i < right; i++){
    if(a[i] == low) m++;
    if(a[i] == high) n++;
  }
  if(m > (right - left)/2) return low;
  if(n > (right - left)/2) return high;
  return -1;
}

int main() {
  int n;
  std::cin >> n;
  vector<int> a(n);
  for (size_t i = 0; i < a.size(); ++i) {
    std::cin >> a[i];
  }
  std::cout << (get_majority_element(a, 0, a.size()) != -1) << '\n';
}

Q3: Improving Quick Sort

快速排序一般是排序算法中最常用的一种方法，但是快排也存在着一个非常大的问题，无法对重复元素进行排序。学习快排的时候这种疑惑困扰了很长一段时间。现在我就来解释一下快排为什么不能处理重复元素。在写快排的过程中，我们一般需要将数组的第一个元素放到这样一个位置，使得这个位置之前的所有元素都比它小，之后的所有元素都比它大。那么如果这个数组从第二个元素到最后一个元素中有一个元素与第一个元素重复，那我们该把它放在哪呢。记住，现在你就是在寻找第一个元素的在数组中的绝对位置。所以你目前还不知道那个重复元素所在的位置，就无法为重复元素定位。

当然还是有解决方法的，那就是三分法。原来一个数组我们将它划分为两部分，左边比目标小，右边比目标大。现在我们使用三分法之后，左边小，中间相等，右边大。当我们二分的时候，返回值为目标元素的应该在的绝对位置，而三分的时候就要返回两个值，分别记录左中间的位置，和中右间的位置，才能使得中间这部分相等的数据不乱。如何返回两个值，当然是使用结构体啦。

一般的快速排序是这样的，i, j分别从左边和右边开始找

从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；

从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；

while(first < last)  
    {  
        while(first < last && a[last] >= key)  
        {  
            --last;  
        }  
   
        a[first] = a[last];  
   
        while(first < last && a[first] <= key)  
        {  
            ++first;  
        }  
           
        a[last] = a[first];  
 }

现在我们有两个变量m1,m2分别记录着左中间位置和中右间位置（初始位置都为0），右边发现比key小的元素，我们就把中右部分其他元素统一向后移动一格，将这个元素插在m1处，注意不能直接交换m1和这个元素的值，因为这样会打乱中右部分的次序。如果发现等于key的值，就放在m2，直接交换就可以了。

以下是代码：

#include <iostream>
#include <vector>
#include <cstdlib>

using namespace std;

struct div3{
  int m1;
  int m2;
};

struct div3 partition3(vector<int> &a, int l, int r) {
  int x = a[l];
  int m1 = l;
  int m2 = l;
  for (int i = l + 1; i <= r; i++) {
    if (a[i] < x) {
      m1++;
      m2++;
      int k = a[i];
      for(int j = i; j > m1 ;j--) a[j] = a[j-1];
      a[m1] = k;
    }
    else if (a[i] == x) {
      m2++;
      swap(a[i], a[m2]);
    }
  }
  swap(a[l], a[m1]);
  struct div3 m;
  m.m1 = m1;
  m.m2 = m2;
  return m;
}


void randomized_quick_sort(vector<int> &a, int l, int r) {
  if (l >= r) {
    return;
  }

  int k = l + rand() % (r - l + 1);
  swap(a[l], a[k]);
  struct div3 m = partition3(a, l, r);

  randomized_quick_sort(a, l, m.m1 - 1);
  randomized_quick_sort(a, m.m2 + 1, r);
}

int main() {
  int n;
  std::cin >> n;
  vector<int> a(n);
  for (size_t i = 0; i < a.size(); ++i) {
    std::cin >> a[i];
  }
  randomized_quick_sort(a, 0, a.size() - 1);
  for (size_t i = 0; i < a.size(); ++i) {
    std::cout << a[i] << ' ';
  }
}

Q4: Number of Inversions

题目意思很简单，找到有多少对 i < j 而 ai 却大于 aj 的（ai, aj)。

当然用O(n^2)也是很容易就实现的事情。

现在要使用分治法降低时间复杂度，

使用分治法的核心就在于怎样合并。

假设我们已经知道了左右各有多少对，

现在除了要把这两项加到sum中，还要计算出左边比右边大的元素对的个数

那么我们如何合并呢：

我们可以参考归并排序（merge-sort），当我们有左右两个有序数组的时候，我们可以将其合并变成一整个有序数组，具体方法可以去百度网上搜索。同样，我们有两个有序数组的时候，假设我们在a数组中发现一个元素比b数组中的一个元素大，那么a数组中这个元素之后的所有元素都比这个元素大，就可以省去很多时间。我的做法就是在归并排序的同时，计算个数。

#include <iostream>
#include <vector>

using namespace std;

long long merge(vector<int> &a, vector<int> &b, size_t left, size_t ave, size_t right) {
  int i = left, j = ave, k = left;
  long long count = 0;
  while((i < ave) && (j < right)){
    if(a[i]<=a[j]) b[k++] = a[i++];
    else{
      b[k++] = a[j++];
      count += ave - i;
    } 
  }

  while(i < ave) b[k++] = a[i++];
  while(j < right) b[k++] = a[j++];
  for(int l = left; l < right; l++){
    a[l] = b[l];
  }
  return count;
}

long long get_number_of_inversions(vector<int> &a, vector<int> &b, size_t left, size_t right) {
  long long number_of_inversions = 0;
  if (right <= left + 1) return number_of_inversions;
  size_t ave = left + (right - left) / 2;
  number_of_inversions += get_number_of_inversions(a, b, left, ave);
  number_of_inversions += get_number_of_inversions(a, b, ave, right);
  number_of_inversions += merge(a, b,left, ave, right);
  return number_of_inversions;
}

int main() {
  int n;
  std::cin >> n;
  vector<int> a(n);
  for (size_t i = 0; i < a.size(); i++) {
    std::cin >> a[i];
  }
  vector<int> b(a.size());
  std::cout << get_number_of_inversions(a, b, 0, a.size()) << '\n';
}

Q5: Organizing a Lottery

算法与数据结构（1.4）：divide and conquer 分治法 (six questions, c++)

简单描述一下题目，给你一组区间和几个数字，问每个数字有多少个区间包含它。

一个很naive的算法就是慢慢数：

vector<int>naive_count_segments(vector<int> starts, vector<int> ends, vector<int> points) {  
  vector<int> cnt(points.size());  
  for (size_t i = 0; i < points.size(); i++) {  
    for (size_t j = 0; j < starts.size(); j++) {  
      cnt[i] += starts[j] <= points[i] && points[i] <= ends[j];  
    }  
  }  
  return cnt;  
}

还是要想办法降低时间复杂度

我们可以将区间的左端点单独排序，

右端点单独排序（排序算法统一按时间复杂度nlogn算）

找出左端点中比key值小的元素的个数，记为l；（使用二分查找，复杂度为logn）

找出右端点中比key值大的元素的个数，记为r；

总个数记为n；

则包含它区间的个数为r+l-n。

这个就需要自己去思考为什么啦。可以举几个例子自己尝试一下对不对。

下面是代码：

#include <iostream>
#include <vector>

using namespace std;

long long merge(vector<int> &a, vector<int> &b, size_t left, size_t ave, size_t right) {
  int i = left, j = ave, k = left;
  long long count = 0;
  while((i < ave) && (j < right)){
    if(a[i]<=a[j]) b[k++] = a[i++];
    else{
      b[k++] = a[j++];
      count += ave - i;
    } 
  }

  while(i < ave) b[k++] = a[i++];
  while(j < right) b[k++] = a[j++];
  for(int l = left; l < right; l++){
    a[l] = b[l];
  }
  return count;
}

long long get_number_of_inversions(vector<int> &a, vector<int> &b, size_t left, size_t right) {
  long long number_of_inversions = 0;
  if (right <= left + 1) return number_of_inversions;
  size_t ave = left + (right - left) / 2;
  number_of_inversions += get_number_of_inversions(a, b, left, ave);
  number_of_inversions += get_number_of_inversions(a, b, ave, right);
  number_of_inversions += merge(a, b,left, ave, right);
  return number_of_inversions;
}

int main() {
  int n;
  std::cin >> n;
  vector<int> a(n);
  for (size_t i = 0; i < a.size(); i++) {
    std::cin >> a[i];
  }
  vector<int> b(a.size());
  std::cout << get_number_of_inversions(a, b, 0, a.size()) << '\n';
}

Q6： Closest Points

算法与数据结构（1.4）：divide and conquer 分治法 (six questions, c++)

这是分治算法中非常非常烧脑的一道题。

按照常规的思路，我们还是将它分成左右两部分，假设我们已经算出了左边的最小点对，和右边的最小的点对，那么如何合并呢？

我们需要寻找左边的一个点和右边的一个点，看看他们之间的距离是否比d1或者d2更小。

首先把距离中间线d (d=min(d1, d2))距离的所有点放到一个数组中

至于紫色区域以外的点就丢弃了，因为左边距中心线距离d以上的点再怎么找，也不可能在右边找到与它距离小于d的点。

现在我们有在紫色区域的点了,记为数组a，然后就要找两个距离最近的，当然也可以使用双重遍历，但时间会很长，我们需要找个简单的方法。

然后把这个数组中的元素按照y值排序，对于每一个a[i]，我们只需要y值与它距离小于d的就行了。这样的点最多有6个，可以根据抽屉原理证明。所以复杂度为6n，加上排序的时间还是nlogn级别的。

下面是代码：

#include <algorithm>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <cmath>
#include <stdlib.h>

using namespace std;

struct point{
  int x;
  int y;
};

int cmp(const void *a, const void *b){
  return (*(const struct point *)a).x - (*(const struct point *)b).x;
}

int cmpy(const void *a, const void *b){
  point *p1 = (point *)a;
  point *p2 = (point *)b;
  return (*(const struct point *)a).y - (*(const struct point *)b).y;
}

double dis(point p1, point p2){
  double d = sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
  return d;
}



double minimal_distance(point p[], int low, int high) {
  //write your code here
  if(low == high - 1) return dis(p[low],p[high]);
  if(low == high - 2) return min(min(dis(p[low],p[high]),dis(p[low],p[low+1])),dis(p[high-1],p[high]));
  int mid = (low + high) / 2;
  double left = minimal_distance(p, low, mid);
  double right = minimal_distance(p, mid+1, high);
  double d;
  d = min(left,right);
  if(d==0) return 0;
  
  point a[high];
  int n=0;
  for(int i = low; i <= high; i++) {
    if(abs(p[i].x - p[mid].x)< d) a[n++]=p[i];
  }

  if(n == 1) return min(left,right);

  qsort(a,n,sizeof(point),cmpy);
  
  double mindis = dis(a[0],a[1]);
  for(int i = 0; i < n; i++){
    for(int j = i+1; j < n && (a[j].y-a[i].y)<mindis; j++){
      if(dis(a[i],a[j]) < mindis) mindis = dis(a[i],a[j]);
    }
  }

  if(d > mindis) return mindis;
  else return d;
}

int main() {
  size_t n;
  std::cin >> n;
  point p[n];
  for (size_t i = 0; i < n; i++) {
    std::cin >> p[i].x >> p[i].y;
  }
  qsort(p,n,sizeof(point),cmp);
  std::cout << std::fixed;
  std::cout << std::setprecision(9) << minimal_distance(p, 0, n-1) << "\n";
}

tips：

关于排序算法，自己编写一般会耗费一些时间，可以直接用c++自带的。性能一般会比自己写的更好，

分为两种：sort&qsort

sort是c++中<algorithm>自带的函数，所以在c++中使用很广泛。具体表现在对stl库支持非常到位，很多容器都可以用sort来排序。

而qsort是c中<stdlib.h>中的函数，只针对c语言中的数组。

实测过程qsort比sort快了不止一倍，在在线编程测试中，有的程序用sort会超时，而用qsort就不会。

那么如果用了c++中的容器又想用qsort怎么办。

qsort(&p[0], size ,sizeof(...),cmp);

可以将qsort的参数改成这样的形式。

同时比较函数具有很严格的格式要求

int cmp(const void *p1, const void *p2){  
    int a = (*(point *)p).x;  
    int b = (*(point *)p).x;  
    return a-b;  
}

这是对第六题结构体排序的cmp函数

具体函数格式可以自行百度。

当然由于vector等容器需要析构什么的很复杂的流程，对容器使用qsort也是明显没有对数组使用qsort来的快的。