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

前言:

  上一节刚讲过归并算法是排序算法中比较少见的一种时间复杂度为:θ(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 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

[vijos]lxhgww的奇思妙想(长链剖分)

首先我们维护出每一个重链头向上$len[i]$个节点是什么,沿着重链走向下$len[i]$个节点是什么

735
来自专栏GIS讲堂

判断是否是数字类

892
来自专栏刘笑江的专栏

learn-haskell

1073
来自专栏韦弦的微信小程序

Swift3 获取String子字符串Substring简单扩展

Swift3更新后不兼容Swift2了,刚开始看Swift,发现好多方法都不能用了啊,那就只能自己摸索了,同时也在这与大家分享分享,正好让大家帮我指正。

592
来自专栏wym

HDU 3018 Ant Trip(欧拉回路)

#include <bits/stdc++.h> using namespace std; const int N=100005; int f[N]; ...

662
来自专栏码农阿宇

C# 获取一个独一无二的字符串 GUID

在保存文件,创建目录时,为了保证名称不重复,经常使用Random产生一个随机数,有更简单且不会重复的办法是: Guid.NewGuid().ToString()...

25210
来自专栏Java Web

狼羊菜过河问题深入学习分析——Java语言描述版

前言 这个问题的抛出,是几个星期之前的算法课程。老师分析了半天,最后的结论是:其实就是图的遍历。那时候挺懵逼的,不管是对于图,还是遍历,或者是数据结构,心里面...

3878
来自专栏恰同学骚年

剑指Offer面试题:9.二进制中1的个数

  一个基本的思路:先判断整数二进制表示中最右边一位是不是1。接着把输入的整数右移一位,此时原来处于从右边数起的第二位被移到最右边了,再判断是不是1。这样每次移...

622
来自专栏Hongten

java的poi技术读取Excel[2003-2007,2010]

这篇blog主要是讲述java中poi读取excel,而excel的版本包括:2003-2007和2010两个版本, 即excel的后缀名为:xls和xlsx。

942
来自专栏菩提树下的杨过

XStream、JAXB 日期(Date)、数字(Number)格式化输出xml

XStream、Jaxb是java中用于对象xml序列化/反序列化 的经典开源项目,利用它们将对象转换成xml时,经常会遇到日期(Date)、数字按指定格式输出...

2127

扫码关注云+社区