【数据结构与算法】四、数组相关算法题

「爱情、让人受尽委屈。」 2023-10-09 14:28 28阅读 0赞

上一篇[【基本数据结构】三、基本的数据结构][Link 1]

## 合并两个有序数组 ##

力扣第88题：

**
     * 力扣第88题：
     * https://leetcode-cn.com/problems/merge-sorted-array/
     * 合并两个有序数组
     */
    public class LeetCodeTest04 {
        
    
    	public static void main(String[] args) {
        
    		//准备数据
    	    int[] arr1 = {
        1,2,3,0,0,0};//{1,2,3,2,5,6}
    	    int[] arr2 = {
        2,5,6};
    //	    int[] arr1 = {2,3,0};
    //	    int[] arr2 = {1};
    	    
    	    System.out.println("合并前的数组1为："+Arrays.toString(arr1));
    	    System.out.println("合并前的数组2为："+Arrays.toString(arr2));
    	    
    //	    mergeArray1(arr1, 3, arr2, 3);
    //	    mergeArray2(arr1, 3, arr2, 3);
    	    mergeArray3(arr1, 2, arr2, 1);
            
    	    
    	    System.out.println("合并后的数组为："+Arrays.toString(arr1));
    	    
    
    	}
    	
    	/**
    	 * 使用暴力方式
    	 * 将两个数组合并后再排序
    	 * 时间复杂度为：O((m+n)*log(m+n))
    	 *  	调用Arrays.sort(arr1);长度为：x ，O(xlogx) 
    	 * 空间复杂度为：O(1)
    	 * @param arr1 需要合并的数组1
    	 * @param m    数组1的长度
    	 * @param arr2 需要合并的数组2
    	 * @param n    数组2的长度
    	 */
    	public static void mergeArray1(int[] arr1, int m, int[] arr2, int n) {
        
    
    	    //将arr2中的数复制到arr1中
    	    System.arraycopy(arr2, 0, arr1, m, n);
    	    //对合并后的数组进行排序
    	    Arrays.sort(arr1);
    	    
        }
    	
    	
    	/**
         * 使用双指针从前往后方式
         * 时间复杂度为：O(m+n)
         * 由于另外开辟了一个数组所以
         * 空间复杂度为：O(m)
         * @param arr1 需要合并的数组1
         * @param m    数组1的长度
         * @param arr2 需要合并的数组2
         * @param n    数组2的长度
         */
        public static void mergeArray2(int[] arr1, int m, int[] arr2, int n) {
        
    
            //由于合并后的数组是arr1，所以需要先将arr1复制一份
            int[] tmpArr = Arrays.copyOf(arr1, m);
            
            /*
             * 定义两个指针分别从arr1和arr2的第一个元素开始比较
             * 方便后续把较小的放进arr1中
             */
            int p1 = 0,p2 = 0;
            
            //声明一个输出数组的下标用于记录
            int index = 0;
            
            //开始将p1和p2不断往后移动比较
            while(p1 < m && p2 < n){
        
                //如果p1下标对应的值更小
                if(tmpArr[p1] < arr2[p2]){
        
                    //将结果数组的下标的值设置为p1下标的值
                    arr1[index] = tmpArr[p1];
                    //p1往后移
                    p1++;
                }else{
        //如果p1下标对应的值大于等于p2小标对应的值
                    //将结果数组的下标的值设置为p2下标的值
                    arr1[index] = arr2[p2];
                    //p2往后移
                    p2++;
                }
                //然后结果数组的下标往后移
                index++;
            }
            /*
             * 遍历完成之后还需处理因无效数字引起的数丢失问题
             * 如果是数组1遍历完毕，则复制数组2的剩余元素到结果数组的尾部
             * 如果是数组2遍历完毕，则复制数组1的剩余元素到结果数组的尾部
             * 其中m+n为结果数组的长度，p1+p2为有效数字的个数
             * 这两个的差即为还有有效数字的个数
             */
            if(p2 >= n){
        
                System.arraycopy(tmpArr, p1, arr1, index, (m + n) - (p1 + p2));
            }
            
            if(p1 >= m){
        
                System.arraycopy(arr2, p2, arr1, index, (m + n) - (p1 + p2));
            }
            
        }
    	
        
        
        /**
         * 使用双指针从后往前方式
         * 时间复杂度为：O(m+n)
         * 空间复杂度为：O(1)
         * @param arr1 需要合并的数组1
         * @param m    数组1的长度
         * @param arr2 需要合并的数组2
         * @param n    数组2的长度
         */
        public static void mergeArray3(int[] arr1, int m, int[] arr2, int n) {
        
            
            /*
             * 定义两个指针分别从arr1和arr2的最后一个元素开始比较
             * 方便后续把较小的放进arr1中
             */
            int p1 = m - 1,p2 = n - 1;
            
            //声明一个输出数组的下标用于记录，这里也是从后至前
            int index = m + n - 1;
            
            //开始将p1和p2不断往前移动比较
            while(p1 >=0 && p2 >= 0){
        
                //由于是从后至前，所以谁大放谁
                if(arr1[p1] >= arr2[p2]){
        
                    arr1[index] = arr1[p1]; 
                    //往前挪动p1
                    p1--;
                }else{
        
                    arr1[index] = arr2[p2];
                    //往前挪动p2
                    p2--;
                }
                //然后结果数组的下标往前移
                index--;
            }
            //同样遍历完成之后还需处理因无效数字引起的数丢失问题
            System.arraycopy(arr2, 0, arr1, 0, p2+1);
        }
    	
    
    }

[Link 1]: https://blog.csdn.net/weixin_43333483/article/details/125628688?spm=1001.2014.3001.5501

发表评论取消回复

表情：

评论列表（有 0 条评论，28人围观）

还没有评论，来说两句吧...

相关阅读

相关面试题(二十四)数据结构与算法

9.1哈希请谈一谈，hashCode() 和equals() 方法的重要性体现在什么地方？考察点：JAVA哈希表参考回答： Java中的HashMap

末蓝、/ 2024年03月27日 16:28/ 0 赞/ 177 阅读

相关数据结构与算法 - 数组

数据结构与算法 - 数组文章目录数据结构与算法 - 数组 1 介绍 2 一维数组的初

待我称王封你为后i/ 2024年03月26日 20:19/ 0 赞/ 183 阅读

相关【数据结构与算法】四、链表相关算法题

上一篇[【数据结构与算法】四、数组相关算法题][Link 1] 数据结构链表的实现思路和方式文章目录 0、单项链表实现 1、反转一个单向链表

布满荆棘的人生/ 2023年10月09日 14:28/ 0 赞/ 114 阅读

相关【数据结构与算法】四、数组相关算法题

上一篇[【基本数据结构】三、基本的数据结构][Link 1] 合并两个有序数组力扣第88题：力扣第88题： https://le

「爱情、让人受尽委屈。」/ 2023年10月09日 14:28/ 0 赞/ 29 阅读

相关数组-数据结构与算法

1.数组是很多编程语言中最基础的数据结构，下面来一起温习下 2.数组示例： int[] a = new int[10]; //定义数组 a[0] = 5

妖狐艹你老母/ 2022年12月27日 07:57/ 0 赞/ 318 阅读

相关【数据结构与算法面试题】数组查找

> 题目来源“[数据结构与算法面试题80道][80]”。 ![这里写图片描述][69baaa339297389045f270d5a796314d.png] 问题分析：时间复

末蓝、/ 2022年10月07日 03:52/ 0 赞/ 291 阅读

相关【数据结构与算法】一数组

数组前面介绍了数据结构与算法的理论知识,下面我们来实践… 数组是一基础的数据结构,在很多语言当中都是被默认支持的.如C++ C\ JAVA等等… C++

浅浅的花香味﹌/ 2022年08月20日 09:14/ 0 赞/ 321 阅读

相关 Java数据结构与算法—数组

本节目标： 1.掌握数组的特点 2.掌握有序数组、无序数组的操作 3.掌握数组中二分查找算法数组在Java中，数组是

àì夳堔傛蜴生んèń/ 2022年05月27日 07:40/ 0 赞/ 423 阅读

相关【算法与数据结构】数组

数组看起来简单基础，但是很多人没有理解这个数据结构的精髓。带着为什么数组要从0开始编号，而不是从1开始的问题，进入主题。 1. 数组如何实现随机访问 1）数组是一种线

妖狐艹你老母/ 2022年05月15日 13:56/ 0 赞/ 345 阅读

相关数据结构与算法-稀疏数组

当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。稀疏数组的处理方法是: 1) 记录数组一共有几行几列，有多少个不同的值

ゞ浴缸里的玫瑰/ 2021年09月24日 17:16/ 0 赞/ 532 阅读