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

前言:

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

相关文章

来自专栏一个会写诗的程序员的博客

《Kotlin极简教程》第3章 Kotlin语言基础第3章 Kotlin语言基础《Kotlin极简教程》正式上架:参考资料

学习任何东西,都是一个由表及里的过程。学习一门编程语言也一样。对于一门编程语言来说,“表” 就是基本词汇(关键字、标识符等)、句子(表达式)和语法。

872
来自专栏一个会写诗的程序员的博客

《Kotlin极简教程》第四章 Kotlin基础语法表达式Null Check循环枚举遍历Map拼接字符串基本类型

在Kotlin中,所有东西都是对象,所以我们可以调用成员函数和属性的任何变量对象。有些类型是内置的,他们的实现被优化过, 但是用户看起来他们就像普通的类. 本节...

643
来自专栏开发与安全

数据结构:栈的链式存储结构

当单链表限定只能在头部进行插入和删除操作的时候,即为链栈,一般我们会将单链表的头指针和栈的栈顶指针top合二为一,通常对链栈来说,是不需要头节点的,因为我们维护...

1828
来自专栏每日一篇技术文章

Swift3.0 - 真的很简单

中文翻译文档 https://github.com/numbbbbb/the-swift-programming-language-in-chinese

541
来自专栏Golang语言社区

Golang精编100题

能力模型 级别模型初级 primary熟悉基本语法,能够看懂代码的意图; 在他人指导下能够完成用户故事的开发,编写的代码符合CleanCode规范;中级 int...

35610
来自专栏云霄雨霁

设计模式----装饰者模式

1120
来自专栏琯琯博客

JavaScript 103 条技能

1、原生JavaScript实现字符串长度截取 function cutstr(str, len) { var temp; var ic...

2286
来自专栏jeremy的技术点滴

py3_cookbook_notes_01

2878
来自专栏nice_每一天

Elasticsearch java api 基本搜索部分详解

使用的是elasticsearch2.4.3版本,在此只是简单介绍搜索部分的api使用

623
来自专栏IMWeb前端团队

Redux 源码解析系列(一) -- Redux的实现思想

Redux 其实是用来帮我们管理状态的一个框架,它暴露给我们四个接口,分别是: createStore combineReducers bindActionCr...

2125

扫描关注云+社区