欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

将两个数组合并排序

程序员文章站 2022-07-13 23:28:11
...

1. 将两个数组合并排序

public void MergeTwoArray() {
        int i = 0;
        int j = 0;
        int k = 0;
        int[] nums1 = new int[] {1,2,3,0,0,0};
        int[] nums2 = new int[] {2,5,6};
        int[] num = new int[nums1.length + nums2.length];
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                num[k++] = nums1[i++];
            } else {
                num[k++] = nums2[j++];
            }
        }
        while (i < nums1.length) {
            num[k++] = nums1[i++];
        }
        while (j < nums2.length) {
            num[k++] = nums2[j++];
        }
        System.out.println(Arrays.toString(num));
    }

【文章参考】int类型的两个数组合并排序

2. 合并两个数组 三种解法

import java.util.Arrays;

import java.util.LinkedList;
/**
 * 合并两个数组      
 * int a[]={0,1,5,6,7,9,14};
 * int b[]={2,4,8,10,13};
 */
public class MergeTwoArray {
	//方法一:
	  private static void method1(int a[],int b[],int array[]) {
		//建立c数组,并将a添加进去  
		int c[]= Arrays.copyOf(a, a.length+b.length);
		//将b数组添加到已经含有a数组的c数组中去
		System.arraycopy(b, 0, c, a.length, b.length);
        //对c数组进行排序
		Arrays.sort(c);
        System.out.println("方法一:");
		for (int i = 0; i < c.length; i++) {
			System.out.print(c[i]+" ");
		}
	}
	 
	  //方法二:集合方法  使用LinkedList 队列
	  private static void method2(int array[],LinkedList<Integer> queue_a,LinkedList<Integer> queue_b ) {
		 //每循环一次,添加一个最小元素进入arrays
		  for (int i = 0; i < array.length; i++) {
			  //两个队列都不为空时,谁小取出谁
			 if (!queue_a.isEmpty()&&!queue_b.isEmpty()) {
				  if (queue_a.peek()<queue_b.peek()) {
					  array[i]=queue_a.poll();
					  continue;
				}else {
					array[i]=queue_b.poll();
					continue;
					}
			}
			 //当数组a为空时,取数组b的元素
				  if (queue_a.isEmpty()&&!queue_b.isEmpty()) {
					array[i]=queue_b.poll();
					continue;
				}
			 //当数组b为空时,取数组a的元素	  
				  if (queue_b.isEmpty()&&!queue_a.isEmpty()) {
					array[i]=queue_a.poll();
					continue;
				}
		}
		System.out.println("方法二:");
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i]+" ");
		}
	}
	
	 //方法三:递归方法
	  private static int [] method3(int a[],int a_start,int b[],int b_start,int array[],int array_start) {
		   
		   //若数组a中的元素都已经放到array数组中,而数组b未全部放到array中,
		   //那么将b中剩余的元素放到array中
           if (a_start>=a.length) {
              	for (int i = array_start; i < array.length; i++) {
					array[array_start]=b[b_start++];
				}
              	return array;
           }
           //若数组b中的元素都已经放到array数组中,而数组a未全部放到array中,
		   //那么将a中剩余的元素放到array中
           if (b_start>=b.length) {
			   for (int i = array_start; i < array.length; i++) {
				    array[array_start]=a[a_start++];
			}
			   return array;
		   }   	
           //将数组的头元素,b数组头元素 中的最小值赋予给array
           if (a[a_start]<b[b_start]) {
			  array[array_start]=a[a_start];
		     return	  method3(a, a_start+1, b, b_start,  array, array_start+1);
		   }else {
			   array[array_start]=b[b_start];
		     return	  method3(a, a_start, b, b_start+1, array, array_start+1); 
		    }
           
		}	
           
	
      public static void main(String[] args) {
		int a[]={0,1,5,6,7,9,14};
		int b[]={2,4,8,10,13};
		LinkedList<Integer> queue_a=new LinkedList<>();
		for (int i = 0; i < a.length; i++) {
			queue_a.offer(a[i]);
		}
		LinkedList<Integer> queue_b=new LinkedList<>();
		for (int i = 0; i < b.length; i++) {
			queue_b.offer(b[i]);
		}
		int array[]=new int[a.length+b.length];
		
		method1(a, b, array);
		System.out.println();
		method2(array, queue_a, queue_b);
		System.out.println("\n方法三:");
		int all[]=method3(a, 0, b, 0, array, 0);
		for (int i : all) {
			System.out.print(i+" ");
		}	
	}
} 

【文章参考】java合并两个数组三种解法

3. LeetCode88 合并两个有序数组

给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。

说明:

  • 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。

  • 可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。

示例:

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

输出: [1,2,2,3,5,6]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/merge-sorted-array


题解

合并两个有序数组


方法一 : 合并后排序

最朴素的解法就是将两个数组合并之后再排序。该算法只需要一行(Java是2行),时间复杂度较差,为O((n+m)log(n+m))。这是由于这种方法没有利用两个数组本身已经有序这一点。

实现

class Solution {
 public void merge(int[] nums1, int m, int[] nums2, int n) {
 System.arraycopy(nums2, 0, nums1, m, n);
 Arrays.sort(nums1);
 }
}

复杂度分析

时间复杂度 : O((n+m)log(n+m))
空间复杂度 : O(1)

方法二 : 双指针 / 从前往后

一般而言,对于有序数组可以通过 双指针法 达到O(n + m)O(n+m)的时间复杂度。

最直接的算法实现是将指针p1置为 nums1的开头,p2nums2 的开头,在每一步将最小值放入输出数组中。

由于 nums1 是用于输出的数组,需要将 nums1 中的前m个元素放在其他地方,也就需要 O(m) 的空间复杂度。
将两个数组合并排序
实现

class Solution {
  public void merge(int[] nums1, int m, int[] nums2, int n) {
    // Make a copy of nums1.
    int [] nums1_copy = new int[m];
    System.arraycopy(nums1, 0, nums1_copy, 0, m);

    // Two get pointers for nums1_copy and nums2.
    int p1 = 0;
    int p2 = 0;

    // Set pointer for nums1
    int p = 0;

    // Compare elements from nums1_copy and nums2
    // and add the smallest one into nums1.
    while ((p1 < m) && (p2 < n))
      nums1[p++] = (nums1_copy[p1] < nums2[p2]) ? nums1_copy[p1++] : nums2[p2++];

    // if there are still elements to add
    if (p1 < m)
      System.arraycopy(nums1_copy, p1, nums1, p1 + p2, m + n - p1 - p2);
    if (p2 < n)
      System.arraycopy(nums2, p2, nums1, p1 + p2, m + n - p1 - p2);
  }
}

复杂度分析

时间复杂度 : O(n + m)
空间复杂度 : O(m)

方法三 : 双指针 / 从后往前

直觉

方法二已经取得了最优的时间复杂度O(n + m),但需要使用额外空间。这是由于在从头改变nums1的值时,需要把nums1中的元素存放在其他位置。

如果我们从结尾开始改写 nums1 的值又会如何呢?这里没有信息,因此不需要额外空间。

这里的指针p 用于追踪添加元素的位置。

将两个数组合并排序
将两个数组合并排序
将两个数组合并排序
将两个数组合并排序
将两个数组合并排序
将两个数组合并排序
将两个数组合并排序
实现

class Solution {
  public void merge(int[] nums1, int m, int[] nums2, int n) {
    // two get pointers for nums1 and nums2
    int p1 = m - 1;
    int p2 = n - 1;
    // set pointer for nums1
    int p = m + n - 1;

    // while there are still elements to compare
    while ((p1 >= 0) && (p2 >= 0))
      // compare two elements from nums1 and nums2 
      // and add the largest one in nums1 
      nums1[p--] = (nums1[p1] < nums2[p2]) ? nums2[p2--] : nums1[p1--];

    // add missing elements from nums2
    System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
  }
}

作者:LeetCode
转载链接:来源:力扣(LeetCode)

相关标签: Java Topic