由归并算法引申出来的其他问题

前言:

  上一节刚讲过归并算法是排序算法中比较少见的一种时间复杂度为:θ(nlgn)的算法。而归并算法之所以快的原因在于它用了分治的思想,现实生活中有很多需要用到分治思想解决的问题,下面就举两个例子。

问题一:

给定一个整数数组和任意整数,找到数组中是否有两数的和等于给定的整数。

  这个问题如果采用穷举法,则大致思路是这样:首先数组的第一个元素与数组剩下的元素相加,看是否有对应的结果。然后再数组第二个元素与除第一个元素和第二个元素本身之外的元素相加... 后面的操作一次类推。很容易得到时间复杂度为:(n-1) + (n-2) + ... + 1 = θ(n2) 。 但其实我们可以借鉴前面归并排序的思想,先对数组进行排序,排完序之后在进行和判断,这时候只要收尾两端各取一个数。如果两数之后大于要找的数,则说明尾数应该前移,如果小于要找的数,则说明前面的数应该后移,如果相等则输出找到的信息,并且避免死循环可以将前一个数后移或者后一个数前移。

  java代码如下:

 1 public class FindEqualSum {
 2 
 3     public static void main(String[] args) {
 4         int[] arr = { 2, 1, 21, 16, 32, 35, 45, 31 };
 5         findEqualSum(arr, 33);
 6     }
 7 
 8     private static void findEqualSum(int[] arr, int num) {
 9         int startIndex = 0;
10         int endIndex = arr.length - 1;
11 
12         // 先进行归并排序,然后再找两数之和
13         divideSort(arr, startIndex, endIndex);
14         findInSorted(arr, startIndex, endIndex, num);
15     }
16 
17     private static void divideSort(int[] arr, int startIndex, int endIndex) {
18         if (startIndex >= endIndex) {
19             return;
20         }
21         int midIndex = (startIndex + endIndex) / 2;
22         divideSort(arr, startIndex, midIndex);
23         divideSort(arr, midIndex + 1, endIndex);
24         merge(arr, startIndex, midIndex, endIndex);
25     }
26 
27     private static void findInSorted(int[] arr, int startIndex, int endIndex,
28             int num) {
29         int i = startIndex;
30         int j = endIndex;
31         while (i < j) {
32             if (arr[i] + arr[j] > num) { // 如果两数之和大于要找的数说明有一个数过大,这时候需要前移后面较大的数
33                 j--;
34             } else if (arr[i] + arr[j] < num) { // 如果两数之和小于要找的数,说明有一个数要小,这时应该后移前面较小的数
35                 i++;
36             } else { // 相等这输出找到的信息,这时候如果需要找到所有需要记住仍要前移后一个数或者后移前一个数,防止死循环。
37                 System.out.println(arr[i] + " + " + arr[j] + " = "
38                         + (arr[i] + arr[j]));
39                 j--;
40             }
41         }
42     }
43 
44     private static void merge(int[] arr, int startIndex, int midIndex,
45             int endIndex) {
46         int k = 0;
47         int i = startIndex;
48         int j = midIndex + 1;
49         int[] newArr = new int[endIndex - startIndex + 1];
50         while (i <= midIndex && j <= endIndex) {
51             if (arr[i] > arr[j]) {
52                 newArr[k++] = arr[j++];
53             } else {
54                 newArr[k++] = arr[i++];
55             }
56         }
57         
58         if (i <= midIndex)
59         {
60             System.arraycopy(arr, i, newArr, k, midIndex - i + 1);
61         }
62         if (j <= endIndex)
63         {
64             System.arraycopy(arr, j, newArr, k, endIndex - j + 1);
65         }
66         System.arraycopy(newArr, 0, arr, startIndex, endIndex - startIndex + 1);
67     }
68 
69 }

问题二:

  假设数组A[n],对于其中的A[i]和A[j],如果i<j, A[i] > A[j].则称两个元素为数组中的逆序对。求任意给定数组的所有逆序对。

  同样的道理:可以通过归并排序的排序过程来进行逆序判断,只要在merge的过程中进行对比就行了。

 1 private static void merge(int[] arr, int startIndex, int midIndex,
 2             int endIndex) {
 3         int k = 0;
 4         int i = startIndex;
 5         int j = midIndex + 1;
 6         int[] newArr = new int[endIndex - startIndex + 1];
 7         while (i <= midIndex && j <= endIndex) {
 8             if (arr[i] > arr[j]) {
 9                 count++;    // 这里用来记录逆序对的个数
10                 newArr[k++] = arr[j++];
11             } else {
12                 newArr[k++] = arr[i++];
13             }
14         }
15         
16         if (i <= midIndex)
17         {
18             System.arraycopy(arr, i, newArr, k, midIndex - i + 1);
19         }
20         if (j <= endIndex)
21         {
22             System.arraycopy(arr, j, newArr, k, endIndex - j + 1);
23         }
24         System.arraycopy(newArr, 0, arr, startIndex, endIndex - startIndex + 1);
25     }

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏深度学习计算机视觉

java用内部类构造链表实现相关方法

代码 import com.sun.corba.se.impl.orbutil.graph.Node; /** * Created by junyi.pc ...

2769
来自专栏ml

uva------(11464)Even Parity

D Even Parity Input: Standard Input Output: Standard Output We...

3646
来自专栏恰同学骚年

剑指Offer面试题:35.将字符串转换为数字

  (3)考虑输入的字符串是否会发生上溢或下溢(正整数的最大值是0x7FFFFFFF,最小的负整数是0x80000000)

985
来自专栏web编程技术分享

【Java框架型项目从入门到装逼】第十节 simple-jdbc源码

40510
来自专栏Golang语言社区

golang使用sort接口实现排序示例

今天看见群里再讨论排序的sort.Interface的实现,有童鞋一直搞不定,我就上手了一下,哦耶搞定了,代码放在这里. 其实很简单sort.Interface...

3737
来自专栏魂祭心

原 js判断旋转中的图片里的元素与背景的某

2868
来自专栏SeanCheney的专栏

《Pandas Cookbook》第01章 Pandas基础

公司网址,http://www.dunderdata.com(dunder是蒸馏朗姆酒的残留液体,取这个名字是类比数据分析过程) GitHub地址:https...

1382
来自专栏有趣的Python

慕课网-C++远征之多态篇(下)-学习笔记

RTTI(运行时类型识别) Run-Time Type Identification typeid < - > dynamic_cast 例子: class F...

3644
来自专栏小灰灰

# Java 一步一步实现高逼格的字符串替换工具(二)

Java 一步一步实现高逼格的字符串替换工具(二) 上一篇实现了一个用于字符串替换的方法,主要是利用 正则 + jdk的字符串替换,本篇则会再之前的基础上...

2166
来自专栏SeanCheney的专栏

《利用Python进行数据分析·第2版》第5章 pandas入门5.1 pandas的数据结构介绍5.2 基本功能5.3 汇总和计算描述统计5.4 总结

pandas是本书后续内容的首选库。它含有使数据清洗和分析工作变得更快更简单的数据结构和操作工具。pandas经常和其它工具一同使用,如数值计算工具NumPy和...

5007

扫码关注云+社区