对两个有序数组进行合并

问题描述:

  数组arr[0...mid-1]和arr[mid..n-1]是各自有序的,对数组arr[0..n-1]的两个有序段进行合并,得到arr[0..n-1]整体。要求空间复杂度为O(1)

  eg:{1,3,5,7,2,4,6}合并成{1,2,3,4,5,6,7}

思路:

方法一

  很显然,看到这个题目就想到了归并中的合并算法,时间复杂度为O(n),但是很可惜空间复杂度也是O(n)不满足要求。但是还是作为一种解决方案提出来吧,具体实现代码就不列了。

方法二

  此外,对于部分有序的我们能想到的是插入排序,但是本题是两段部分有序合并在一起,进行插入排序的话时间复杂度也是O(n2),空间复杂度满足条件。

方法三

  本方法的思路有点类似简单排序的,具体思路如下:

  1. 遍历数组中下标为0~mid-1的元素,将遍历到的元素的值与arr[mid]比较,若arr[i]大于arr[mid],则交换,即第i次排序,将其最右边的最小的值放到arr[i]的位子上,
  2. 然后在后半段中将arr[mid]排序到正常的位置上去。
 1   public static void merge(int [] arr,int mid){
 2         int len = arr.length ;
 3         int temp ;
 4         for(int i = 0 ; i < mid ; i++){
 5                 if(arr[i] > arr[mid]){
 6                 temp = arr[i] ;
 7                 arr[i] = arr[mid] ;
 8                 arr[mid] = arr[i] ;
 9             }
10             
11             for(int j = mid + 1 ; j < len ; j++){
12                 if(arr[j] < arr[j-1]){
13                     temp = arr[j] ;
14                     arr[j] = arr[j-1] ;
15                     arr[j-1] = arr[j] ;
16                 }else{                    
17                     break ;
18                 }
19             }
20         }

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏python3

python3--函数进阶

TypeError: func() missing 4 required keyword-only arguments: 'a', 'b', 'c', and ...

951
来自专栏码云1024

Java 程序运行过程中的内存分析

3216
来自专栏linux驱动个人学习

typeof关键字的作用

一、typeof详解: 前言:     typeof关键字是C语言中的一个新扩展,这个特性在linux内核中应用非常广泛。(其实这和C++的auto关键字和可以...

3375
来自专栏吾爱乐享

java之学习集合的基本功能测试及案例分析

1293
来自专栏星汉技术

原 荐 Scala的面向对象

----------目录--------------------------------------------------------- 1.Scala简介和...

30713
来自专栏wym

HDU 6109 数据分割(并查集+set维护)

 题目:http://acm.hdu.edu.cn/showproblem.php?pid=6109

1201
来自专栏老司机的技术博客

宝宝都能学会的python编程教程10:调用函数

python里的函数和数学意义上的函数并没有太大差别。 调用函数 python内置了很多有用的函数,我们可以直接调用。 要调用一个函数,需要知道函数的名称和参数...

3344
来自专栏用户画像

正则表达式匹配 整数和正整数

?匹配前面的子表达式零次或一次,或指明一个非贪婪限定符。要匹配 ? 字符,请使用 \?

842
来自专栏Java帮帮-微信公众号-技术文章全总结

04.Java对象和类

04.Java对象和类 Java 对象和类 Java作为一种面向对象语言。支持以下基本概念: 多态 继承 封装 抽象 类 对象 实例 方法 重载 本节我们重点研...

4586
来自专栏遊俠扎彪

C++中的字符数组、字符串、字符指针的一些笔记

1、sizeof会计算实际内存空间,strlen会计算C风格的字符串的实际字符数(不包括\0)。

19610

扫码关注云+社区

领取腾讯云代金券