专栏首页aCloudDeveloper算法导论2-9章补充几道题

算法导论2-9章补充几道题

本篇博文意在对前几章中遗漏的,本人觉得有意思的习题当独拿出来练练手。

1、习题2-4,求逆序对,时间复杂度要求Θ(nlgn)

定义:对于一个有n个不同的数组A, 当i<j时,存在A[i]>A[j],则称对偶(i, j)为A的一个逆序对。

譬如:<2,3,8,6,1>有5个逆序对。

解题思路:归并排序的思想:逆序对的数量=左区间的逆序对+右区间的逆序对+合并的逆序对

代码如下:

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int MergeInversion(int arr[], int nLeft, int nRight);
 6 int Merge(int arr[], int p, int q, int r);
 7 
 8 //用归并排序找逆序对
 9 int MergeInversion(int arr[], int nLeft, int nRight)
10 {
11     int nInversion = 0;
12     if (nLeft < nRight) {
13         int nMid = (nLeft+nRight) >> 1;
14         nInversion += MergeInversion(arr, nLeft, nMid);
15         nInversion += MergeInversion(arr, nMid+1, nRight);
16         nInversion += Merge(arr, nLeft, nMid, nRight);
17     }
18     return nInversion;
19 }
20 
21 int Merge(int arr[], int p, int q, int r)
22 {
23     int n1 = q - p + 1;
24     int n2 = r - q;
25     int *left = new int[n1];
26     int *right = new int[n2];
27 
28     int i,j;
29     for (i = 0; i < n1; i ++)
30         left[i] = arr[p+i];
31     for (j = 0; j < n2; j ++)
32         right[j] = arr[q+1+j];
33 
34     i = 0;
35     j = 0;
36     int k = p;
37     int nInverCount = 0; //逆序对的数目
38 
39     while (i < n1 && j < n2) {
40         if (left[i] <= right[j]) 
41             arr[k++] = left[i++];
42         else {//假如左边子序列的数大于右子序列,则逆序对数为n1 - i;
43             arr[k++] = right[j++];
44             nInverCount += (n1 - i);
45         }
46     }
47     while (i < n1)
48         arr[k++] = left[i++];
49     while (j < n2)
50         arr[k++] = right[j++];
51     
52     delete left;
53     left = NULL;
54     delete right;
55     right = NULL;
56     
57     return nInverCount;
58 }
59 
60 int main()
61 {
62     int arr[] = {2,3,8,6,1};
63     int len = sizeof(arr)/sizeof(arr[0]);
64 
65     int *arrT = new int[len];
66     
67 
68     cout << MergeInversion1(arr, 0, 4, arrT) << endl;
69     for (int i = 0; i < 5; i++)
70         cout << arrT[i] << " ";
71     return 0;
72 }

2、习题9.3-7,设计一个O(n)时间的算法,对于一个给定的包含n个互异元素的集合S和一个正整数 k<=n,该算法能够确定S中最接近中位数的k个元素。

譬如数组:<5,7,10,3,6,2,8,9,1,11,12>,中位数为6,如果k=3,最接近6的3个元素是<5,7,4>或<5,7,8>;如果k=4,则最接近6的4个元素是<5,7,4,8>。

解题思路:

1)通过Select()得到A的中位数 --->O(n)

2)计算A中每个数到中位数的差值作为数组D ,并增加D的一个副本D‘ --->O(n)

3)通过Select()得到D’中第k大的数 ---> O(n)

4)依次遍历D中的数,判断比k小的k个数,即为所求 ---> <O(n)

代码如下:

 1 #include <iostream>
 2 #include <cassert>
 3 #include <cmath>
 4 using namespace std;
 5 
 6 int* K_Select(int arr[], int nLen, int k);
 7 int Select(int arr[], int nLeft, int nRight, int nMin);
 8 int Partition(int arr[], int p, int r);
 9 void Swap(int &n, int &m);
10 
11 int* K_Select(int arr[], int nLen, int k)
12 {
13     assert(k <= nLen);
14     
15     int *pDis = new int[nLen-1]; //the distance of every bit and median
16     int *pDis_cpy = new int[nLen-1];
17     int *pKArr = new int[k]; //return k_array
18 
19     int nMedian = Select(arr, 0, nLen-1, nLen/2); //get the median of arr
20     int iMedian;
21     int nDLen = 0;
22     for (int i = 0; i < nLen; i ++) {
23         if (arr[i] != nMedian)
24             pDis[nDLen++] = abs(arr[i]-nMedian); //get the distance using abs()
25         else
26             iMedian = i; //get the index of median
27     }
28     memcpy(pDis_cpy, pDis, sizeof(int)*(nLen-1)); //copy the distance    
29     int nKMedian = Select(pDis_cpy, 0, nDLen-1, k); //get the k-th minimum distance between median and every bit
30     
31     delete pDis_cpy;
32     pDis_cpy = NULL;
33 
34     int ik = 0;
35     for (int i = 0; ik < k && i < nDLen; i ++) {
36         if (pDis[i] <= nKMedian) {
37             if (i < iMedian) //judge the index of array and the index of median
38                 pKArr[ik++] = nMedian - pDis[i];
39             else
40                 pKArr[ik++] = nMedian + pDis[i];
41         }
42     }
43 
44     delete pDis;
45     pDis = NULL;
46 
47     return pKArr;
48 }
49 
50 int Select(int arr[], int nLeft, int nRight, int nMin)
51 {
52     assert(nLeft <= nRight);
53     assert(nMin <= nRight-nLeft+1);
54 
55     if (nLeft == nRight)
56         return arr[nLeft];
57     int nMid = Partition(arr, nLeft, nRight);
58     int k = nMid - nLeft + 1;
59     if (k == nMin)
60         return arr[nMid];
61     else if (k > nMin)
62         return Select(arr, nLeft, nMid-1,nMin);
63     else
64         return Select(arr, nMid+1, nRight, nMin-k);
65 }
66 
67 int Partition(int arr[], int p, int r)
68 {
69     assert(p <= r);
70 
71     int nTemp = arr[r];
72     int i = p - 1, j = p;
73     while(j < r) {
74         if (arr[j] <= nTemp) {
75             Swap(arr[i+1], arr[j]);
76             i ++;
77         }
78         j ++;
79     }
80     Swap(arr[i+1], arr[r]);
81     return i+1;
82 }
83 
84 void Swap(int &n, int &m)
85 {
86     int t = n;
87     n = m;
88     m = t;
89 }
90 
91 int main()
92 {
93     int arr[] = {5,7,10,3,6,2,8,9,4,1,11,12};
94     int *karr = K_Select(arr, 12, 4);
95     for (int i=0; i < 4; i ++)
96         cout << karr[i] << " ";
97     return 0;
98 }

3、习题9.3-8,求两个有序数组的中位数?

题目:设X[1...n]和Y[1...n]为两个数组,每个都包含n个有序的元素。请设计一个O(lgn)时间的算法来找出数组X 和Y中所有2n个元素的中位数。

譬如:X:<1,2,3,4,7,9>; Y:<2,5,6,7,10,11>; 中位数为数组Y中的6.

解题思路:二分查找思想--->O(lgn)

1)如果两个数组均只有一个元素,则返回数组中的较小值。

2)两个数组有2n个元素,则中位数位于n index,小于中位数的元素个数为n-1;

3)如果当前找到中位数在数组X中的标号为 K,则在数组Y的标号为:n-K-2 < index <= n-K-1;

4)如果当前在数组X中找到的中位数 X[K]<= Y[n-K-2],说明该数小了,应该在X的右区间[mid+1, right]继续找,反之,如果X[K] > Y[n-K-1],说明该数大了,应该在X的左区间[left, mid-1]继续找。

5)如果重复该过程,没有在X中找到该中位数,则采用同样的方法在Y中找。

代码如下:

 1 #include <iostream>
 2 #include <cassert>
 3 using namespace std;
 4 
 5 int SelectMedian(int *arrA, int *arrB, int left, int right)
 6 {
 7     assert(NULL != arrA);
 8     assert(NULL != arrB);
 9     
10     int nLen = right-left+1;
11 
12     while (left <= right) {
13         int mid = (left+right)/2;
14 
15         if (mid == nLen-1 && arrA[mid] <= arrB[0]) //only one element
16             return arrA[mid];
17         else if (mid < nLen-1) {
18             if(arrA[mid] <= arrB[nLen-mid] && arrA[mid] > arrB[nLen-1-mid]) //K = nLen-1-K note:from 0 index
19                 return arrA[mid];
20             else if (arrA[mid] <= arrB[nLen-1-mid]) //if the element is small, find it in right region.
21                 left = mid + 1;
22             else         //if the element is big, find it in left region.
23                 right = mid - 1;
24         }
25     }
26     return -1;
27 }
28 
29 //find the median of two array: arrA and arrB
30 //return the median of two array
31 void TwoArrMedian(int *arrA, int *arrB, int nLen)
32 {
33     assert(NULL != arrA);
34     assert(NULL != arrB);
35     
36     int nMedian;
37     if (SelectMedian(arrA, arrB, 0, nLen-1) == -1) //not find
38         nMedian = SelectMedian(arrB, arrA, 0, nLen-1);
39     
40     cout << nMedian << endl;
41 }
42 
43 int main()
44 {
45     int a[] = {1,2,3,4,8,9,13};
46     int b[] = {2,5,6,7,10,11,12};
47 
48     TwoArrMedian(a, b, 7);
49     return 0;
50 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法导论第二章小试牛刀

    Author: bakari   Date: 2015.9.11 《算法导论》真是一本让人又爱又恨的书,爱自然是因为它精简凝练的算法呈现,读来让人欲罢不能;至于...

    CloudDeveloper
  • Pascal三角形

    作者:bakari   时间:2012.8.4 Pascal三角形又称杨辉三角形,是多项式系数的一种规律展示,最早是由我国数学家杨辉发现,比Pascal早200...

    CloudDeveloper
  • LeetCode:105_Construct Binary Tree from Preorder and Inorder Traversal | 根据前序和中序遍历构建二叉树 | Medium

    要求:通过二叉树的前序和中序遍历序列构建一颗二叉树 代码如下: 1 struct TreeNode { 2 int val; ...

    CloudDeveloper
  • 3117 高精度乘法

    3117 高精度练习之乘法  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解 题目描述 Description 给出...

    attack
  • 洛谷P1043 数字游戏

    题目描述 丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单,但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的,在你面前...

    attack
  • HDU 1573 X问题

    Problem Description 求在小于等于N的正整数中有多少个X满足: Input 输入数据的第一行为一个正整数T,表示有T组测试数据。每组测...

    attack
  • Day2上午解题报告

    预计分数:100+0+60=160 实际分数:100+0+60=160 mmpT1数据错了。。。 T1遭遇 题目描述 你是能看到第一题的 friends呢。 —...

    attack
  • 洛谷P4180 [Beijing2010组队]次小生成树Tree

    题目描述 小C最近学了很多最小生成树的算法,Prim算法、Kurskal算法、消圈算法等等。正当小C洋洋得意之时,小P又来泼小C冷水了。小P说,让小C求出一个无...

    attack
  • LeetCode 第 210 场周赛 解题报告

    那么在遍历过程中,栈中元素数量的最大值即为答案。栈中的(可以理解为还没遍历到匹配的),即那些嵌套的(。

    ACM算法日常
  • 次小生成树

    次小生成树 次小生成树 我们已经熟知了求最小生成树的方法,用kruskal,prim算法都可以搞 那么我们如何求次小生成树呢? 这里次小生成树的定义是 边...

    attack

扫码关注云+社区

领取腾讯云代金券