Java 中不使用额外空间合并两个排序数组

2024年9月10日 | 阅读13分钟

我们有两个包含整数的数组。这两个数组都按升序排序。我们的任务是显示两个已排序数组的所有元素，以便所有元素都按升序显示。请注意，不允许使用任何额外的空间来存储元素。换句话说，程序的空间复杂度应始终为常数。

示例 1

输入

int inArr1[] = {1, 3, 7, 9, 15, 20}
int inArr2[] = {2, 5, 8, 11, 14, 16, 18, 19}

输出

{1, 2, 3, 5, 7, 8, 9, 11, 14, 15, 16, 18, 19, 20}

解释

当我们将两个数组按升序合并时，得到上面的输出。

示例 2

输入

int inArr1[] = {-11, -5, -3, 1, 5, 15, 25, 30, 40, 45}
int inArr2[] = {-30, -25, -19, -10, -1, 7, 20, 29, 35}

输出

{-30, -25, -19, -11, -10, -5, -3, -1, 1, 5, 7, 15, 20, 25, 29, 30, 35, 40, 45}

解释

当我们将两个数组按升序合并时，得到上面的输出。

简单方法：暴力法和排序

如果允许使用额外空间，我们可以轻松创建一个大小等于输入数组大小之和的数组，然后使用两个指针将所有元素以升序放入构造的数组中。但是，问题说明不允许使用额外空间。因此，我们必须使用输入数组的空间。我们所要做的就是将前 m 个最小的元素放入第一个输入数组中。其余 n 个元素应放入第二个输入数组中。然后对第二个数组进行排序，因为第一个数组在此过程中将是已排序的。之后，使用 for 循环显示两个数组中的所有元素。请注意，这里的 m = 第一个输入数组的大小，n = 第二个输入数组的大小。

算法

对于 'j' 从 0 到 'm - 1'
- flg = j
- least = inArr1[j]
- 对于 'k' 从 'j' 到 'm - 1'
  - if(inArr1[k] < least)
    - least = inArr1[k]
    - flg = k
  - 对于 'k' 从 '0' 到 'n - 1'
  - if(inArr2[k] < least)
  - least = inArr2[k]
  - flg = k
- 将 'inArr1[j]' 与 'least' 元素交换。
对数组 'inArr2' 进行排序。

现在观察以下程序。

文件名： MergeSortedArr.java

// importing Arrays for doing the sorting
import java.util.Arrays;

public class MergeSortedArr 
{
// a method for merging two sorted arrays inArr1 and inArr2 without any extra space
public void mergeTwoSortedArrWithoutExtraSpace(int inArr1[], int inArr2[])
{
// computing size of the input arrays
int m = inArr1.length;
int n = inArr2.length;

// Iterating over the input arrays
// and putting the first m smallest element
// in the input array inArr1. 
for(int j = 0; j < m; j++)
{
    int flg = j;
    int least = inArr1[j];

    // Computing the minimum among the rest of the elements of 'inArr1'.
    for(int k = j; k < m; k++)
    {
        if(inArr1[k] < least)
        {
            least = inArr1[k];
            flg = k;
        }
    }

    // Computing the minimum among the elements of 'inArr2'.
    for(int i = 0; i < n; i++)
    {
        if(inArr2[i] < least)
        {
            least = inArr2[i];
            flg = i;
        }
    }

    // Swapping 'inArr1[j]' with the minimum element.
    if(flg < m && flg >= j && inArr1[flg] == least)
    {
       swapEle(inArr1, inArr1, j, flg); 
    }
        
    else
    {
        swapEle(inArr1, inArr2, j, flg);
    }
}

    // Sorting the array 'inArr2'.
    Arrays.sort(inArr2);
}
    // method for swapping two integers 'a1' and 'a2'.
    public static void swapEle(int inArr1[], int inArr2[], int a1, int a2)
    {
        int tmp = inArr1[a1];
        inArr1[a1] = inArr2[a2];
        inArr2[a2] = tmp;
    }
    
// main method
public static void main(String argvs[]) 
{
// creating an object of the class MergeSortedArr
MergeSortedArr obj = new MergeSortedArr();

// input arrays
int inArr1[] = {1, 3, 7, 9, 15, 20};
int inArr2[] = {2, 5, 8, 11, 14, 16, 18, 19};

int sze1 = inArr1.length; // computing size of the first input array
int sze2 = inArr2.length; // computing size of the second input array

System.out.println("The input arrays are: ");
for(int i = 0 ; i < sze1; i++)
{
System.out.print(inArr1[i] + " ");
}
System.out.println( );
for(int i = 0 ; i < sze2; i++)
{
System.out.print(inArr2[i] + " ");
}
// invoking the method mergeTwoSortedArrWithoutExtraSpace() for merging the 
// array without any extra space
obj.mergeTwoSortedArrWithoutExtraSpace(inArr1, inArr2);
System.out.println( );

System.out.println("After merging the sorted arrays, we get: ");
for(int i = 0 ; i < sze1; i++)
{
System.out.print(inArr1[i] + " ");
}
for(int i = 0 ; i < sze2; i++)
{
System.out.print(inArr2[i] + " ");
}
System.out.println( "\n" );

// input arrays
int inArr3[] = {-11, -5, -3, 1, 5, 15, 25, 30, 40, 45};
int inArr4[] = {-30, -25, -19, -10, -1, 7, 20, 29, 35};

int sze3 = inArr3.length; // computing size of the third input array
int sze4 = inArr4.length; // computing size of the fourth input array

System.out.println("The input arrays are: ");
for(int i = 0 ; i < sze3; i++)
{
System.out.print(inArr3[i] + " ");
}
System.out.println( );
for(int i = 0 ; i < sze4; i++)
{
System.out.print(inArr4[i] + " ");
}

// invoking the method mergeTwoSortedArrWithoutExtraSpace() for merging the 
// array without any extra space
obj.mergeTwoSortedArrWithoutExtraSpace(inArr3, inArr4);
System.out.println( );
System.out.println("After merging the sorted arrays, we get: ");
for(int i = 0 ; i < sze3; i++)
{
System.out.print(inArr3[i] + " ");
}
for(int i = 0 ; i < sze4; i++)
{
System.out.print(inArr4[i] + " ");
}

}

}  

输出

The input arrays are: 
1 3 7 9 15 20 
2 5 8 11 14 16 18 19 
After merging the sorted arrays, we get: 
1 2 3 5 7 8 9 11 14 15 16 18 19 20 

The input arrays are: 
-11 -5 -3 1 5 15 25 30 40 45 
-30 -25 -19 -10 -1 7 20 29 35 
After merging the sorted arrays, we get: 
-30 -25 -19 -11 -10 -5 -3 -1 1 5 7 15 20 25 29 30 35 40 45

复杂度分析：第一个数组 inArr1[] 以 O(m) 的时间遍历，对于 inArr1[] 中的每个元素，我们都遍历 inArr1[] 的其余位置以及 inArr2[] 的所有位置。因此，程序的总体时间复杂度为 O(m x (m + n))。该程序不使用额外空间。因此，程序的空间复杂度为 O(1)。

另一种方法：使用双指针和排序

在这里，我们将 'm' 个最小的数字保留在 'inArr1[]' 中（可能已排序，也可能未排序），其余元素保留在 'inArr2[]' 中（可能已排序，也可能未排序）。我们分别使用两个指针 'p' = 0 和 'q' = 0 来遍历 'inArr1[]' 和 'inArr2[]'。如果 'inArr1[p]' 等于或大于 'inArr2[q]'，则我们将 'inArr1[]' 的某个 'k' 位置的元素与 'inArr2[q]' 交换，并增加 'q'，否则，我们增加 'p'。将 'inArr1[]' 中最大的元素替换是有意义的。因此，我们初始化 'k' = 'm - 1'。之后，我们在每次交换后减少 'k'。最后，我们对 'inArr1[]' 和 'inArr2[]' 进行排序。

算法

p = 0, q = 0, k = m - 1
while(p <= k and q < N)
- if(inArr1[p] < inArr2[q])
  - p++
- else
  - swapEle(inArr1[k], inArr2[q])
  - q = q + 1
  - k = k - 1
将 'inArr1[]' 按非递减顺序排序。
将 'inArr2[]' 按非递减顺序排序。

现在，观察以下实现。

文件名： MergeSortedArr1.java

// importing Arrays for doing the sorting
import java.util.Arrays;

public class MergeSortedArr1 
{
// a method for merging two sorted arrays inArr1 and inArr2 without any extra space
public void mergeTwoSortedArrWithoutExtraSpace(int inArr1[], int inArr2[])
{
// computing size of the input arrays
int m = inArr1.length;
int n = inArr2.length;
int p = 0; int q = 0;
int k = m - 1;

// Iterating over the elements of 'inArr1[]' and 'inArr2[]'.
while(q <= k && q < n)
{
    if(inArr1[p] < inArr2[q])
    {
        p = p + 1;
    }
    else
    {

        // Swapping the current elements of 'inArr2[]' 
        // with the 'kth' element of 'inArr1[]'.
        swapEle(inArr1, inArr2, k, q);
        q = q + 1;
        k = k - 1;
    }
}

// Sorting the array 'inArr1'.
Arrays.sort(inArr1);

// Sorting the array 'inArr2'.
Arrays.sort(inArr2);
}
    // method for swapping two integers 'a1' and 'a2'.
    public static void swapEle(int inArr1[], int inArr2[], int a1, int a2)
    {
        int tmp = inArr1[a1];
        inArr1[a1] = inArr2[a2];
        inArr2[a2] = tmp;
    }
    
// main method
public static void main(String argvs[]) 
{
// creating an object of the class MergeSortedArr1
MergeSortedArr1 obj = new MergeSortedArr1();

// input arrays
int inArr1[] = {1, 3, 7, 9, 15, 20};
int inArr2[] = {2, 5, 8, 11, 14, 16, 18, 19};

int sze1 = inArr1.length; // computing size of the first input array
int sze2 = inArr2.length; // computing size of the second input array

System.out.println("The input arrays are: ");
for(int i = 0 ; i < sze1; i++)
{
System.out.print(inArr1[i] + " ");
}
System.out.println( );
for(int i = 0 ; i < sze2; i++)
{
System.out.print(inArr2[i] + " ");
}
// invoking the method mergeTwoSortedArrWithoutExtraSpace() for merging the 
// array without any extra space
obj.mergeTwoSortedArrWithoutExtraSpace(inArr1, inArr2);
System.out.println( );

System.out.println("After merging the sorted arrays, we get: ");
for(int i = 0 ; i < sze1; i++)
{
System.out.print(inArr1[i] + " ");
}
for(int i = 0 ; i < sze2; i++)
{
System.out.print(inArr2[i] + " ");
}
System.out.println( "\n" );

// input arrays
int inArr3[] = {-11, -5, -3, 1, 5, 15, 25, 30, 40, 45};
int inArr4[] = {-30, -25, -19, -10, -1, 7, 20, 29, 35};

int sze3 = inArr3.length; // computing size of the third input array
int sze4 = inArr4.length; // computing size of the fourth input array

System.out.println("The input arrays are: ");
for(int i = 0 ; i < sze3; i++)
{
System.out.print(inArr3[i] + " ");
}
System.out.println( );
for(int i = 0 ; i < sze4; i++)
{
System.out.print(inArr4[i] + " ");
}

// invoking the method mergeTwoSortedArrWithoutExtraSpace() for merging the 
// array without any extra space
obj.mergeTwoSortedArrWithoutExtraSpace(inArr3, inArr4);
System.out.println( );
System.out.println("After merging the sorted arrays, we get: ");
for(int i = 0 ; i < sze3; i++)
{
System.out.print(inArr3[i] + " ");
}
for(int i = 0 ; i < sze4; i++)
{
System.out.print(inArr4[i] + " ");
}

}

}

输出

The input arrays are: 
1 3 7 9 15 20 
2 5 8 11 14 16 18 19 
After merging the sorted arrays, we get: 
1 2 3 5 7 8 9 11 14 15 16 18 19 20 

The input arrays are: 
-11 -5 -3 1 5 15 25 30 40 45 
-30 -25 -19 -10 -1 7 20 29 35 
After merging the sorted arrays, we get: 
-30 -25 -19 -11 -10 -5 -3 -1 1 5 7 15 20 25 29 30 35 40 45

复杂度分析：我们以 O(m + n) 的时间遍历 'inArr1[]' 和 'inArr2[]'，元素交换 Takes O(1) 时间。对 'inArr1[]' 和 'inArr2[]' 的排序分别需要 O(m x log(m)) 和 O(n x log(n)) 的时间。因此，上述程序的总体时间复杂度为 O(m + n + m x log(m) + n x log(n))。该程序的空间复杂度为 O(1)，因为没有使用额外空间。

另一种方法：使用欧几里得除法引理

在此方法中，我们将进行交换，而无需在最后对数组进行排序。我们将把最小的数字填充到最小的位置，而不是像方法 2那样将它们放在最后的位置（即，我们将从 'k' = 0 开始，而不是 'k' = 'm - 1'）。但是，在这种情况下，'inArr1[]' 中的某个数字可能会被第二个数组 'inArr2[]' 中的某些数字替换。但是，很有可能它将在 'inArr1[]' 中的稍后位置被利用。因此，有必要提取最初位于位置 'k' 的数字，以防它先前被替换。

我们可以通过以下方式使用欧几里得引理

从数字 M = X * R + P，我们可以通过将 'M' 除以 'R' 来获得 'X'，并通过将 'M' 对 'R' 取模来获得 'P'。

我们将 MAX = 10⁹ + 1 选择为整个数组 'inArr1[]' 的 'R'。

我们使用两个指针 'p' 和 'q' 遍历 'inArr1[]' 和 'inArr2[]' 的元素。将位置初始化为 'k' = 0。我们检查 'inArr1[p]' 和 'inArr2[q]' 处最初放置的数字。我们比较它们，并将 'inArr1[k]' 或 'inArr2[k - m]' 增加最小的两个原始数字乘以 'MAX' 的乘积。如果来自 'inArr2[]' 的数字较小，则增加 'q'。否则，我们增加 'p'。

类似地，我们更新所有 'k' 从 0 到 'm + n - 1' 的值。

最后，我们遍历 'inArr1[]' 和 'inArr2[]' 并将所有数字除以 'R' 来获得合并后的数组。

算法

分配 MAX = 10⁹ + 1
p = 0, q = 0, k = m - 1
while(p < m and q < n and k < m + n)
- orgNum1 = inArr1[p] % MAX
- orgNum2 = inArr2[q] % MAX
- if(orgNum1 <= orgNum2)
  - if(k < m)
    - inArr1[k] = inArr1[k] + (orgNum1 * MAX)
  - else
    - inArr2[k - m] = inArr2[k - m] + (orgNum1 * MAX)
  - p = p + 1
  - k = k + 1
- else
  - if(k < m)
  - inArr1[k] = inArr1[k] + orgNum2 * MAX
  - else
    - inArr2[k - m] = inArr2[k - m] + orgNum2 * MAX
  - q = q + 1
  - k = k + 1
- while(q < n)
  - orgNum2 = inArr2[q] % MAX
  - if(k < m)
    - inArr1[k] += orgNum2 * MAX
  - else
    - inArr2[k - m] += orgNum2 * MAX
  - q = q + 1
  - k = k + 1
- while(p < m)
  - orgNum1 = inArr1[p] % MAX
  - if(k < m)
    - inArr1[k] = inArr1[k] + (orgNum1 * MAX)
  - else
    - inArr2[k - m] = inArr2[k - m] + orgNum2 * MAX
  - p = p + 1
  - k = k + 1
- 对于 'p' 从 0 到 'm - 1'
  - inArr1[p] = inArr1[p] / MAX
- 对于 'q' 从 0 到 'n - 1'
  - inArr2[q] = inArr2[q] / MAX

现在，让我们观察以下实现。

文件名： MergeSortedArr2.java

public class MergeSortedArr2 
{
// a method for merging two sorted arrays inArr1 and inArr2 without any extra space
public void mergeTwoSortedArrWithoutExtraSpace(long inArr1[], long inArr2[])
{
// computing size of the input arrays
int m = inArr1.length;
int n = inArr2.length;
int p = 0; int q = 0;
int k = 0;

// Maximum element we will use for Euclid's Lemma.
long MAX = 1000000007;

// Iterating over the elements of 'inArr1' and 'inArr2'.
while(p < m && q < n && k < m + n)
{

    // Extracting the original numbers.
    long orgNum1 = inArr1[p] % MAX;
    long orgNum2 = inArr2[q] % MAX;

    // Comparing the original numbers.
    if(orgNum1 <= orgNum2)
    {
        if(k < m)
        {
            inArr1[k] = inArr1[k] + (orgNum1 * MAX);
        }
        else
        {
            inArr2[k - m] = inArr2[k - m] + (orgNum1 * MAX);
        }
        p = p + 1;
        k = k + 1;
    }
    else
    {
        if(k < m)
        {
            inArr1[k] = inArr1[k] + (orgNum2 * MAX);
        }
        else
        {
            inArr2[k - m] = inArr2[k - m] + (orgNum2 * MAX);
        }
        q = q + 1;
        k = k + 1;
    }
}

// Iterating over the remaining elements of 'B' (if any).
while(q < n)
{
    long orgNum2 = inArr2[q] % MAX;
    if(k < m)
    {
        inArr1[k] = inArr1[k] + (orgNum2 * MAX);
    }
    else
    {
        inArr2[k - m] = inArr2[k - m] + (orgNum2 * MAX);
    }
    q = q + 1;
    k = k + 1;
}

// Iterating over the rest of the elements of 'inArr1[]' (if any).
while(p < m)
{
    long orgNum1 = inArr1[p] % MAX;
    if(k < m)
    {
        inArr1[k] = inArr1[k] + (orgNum1 * MAX);
    }
    else
    {
        inArr2[k - m] = inArr2[k - m] + (orgNum1 * MAX);
    }
    p = p + 1;
    k = k + 1;
}

// Changing the elements present in the array 'inArr1[]' to the new numbers.
for(int l = 0; l < m; ++l)
{
    inArr1[l] = inArr1[l] / MAX;
}

// Changing the elements present in the array 'inArr2[]' to the new numbers.
for(int l = 0; l < n; ++l)
{
    inArr2[l] = inArr2[l] / MAX;
}
}

    
// main method
public static void main(String argvs[]) 
{
// creating an object of the class MergeSortedArr2
MergeSortedArr2 obj = new MergeSortedArr2();

// input arrays
long inArr1[] = {1, 3, 7, 9, 15, 20};
long inArr2[] = {2, 5, 8, 11, 14, 16, 18, 19};

int sze1 = inArr1.length; // computing size of the first input array
int sze2 = inArr2.length; // computing size of the second input array

System.out.println("The input arrays are: ");
for(int i = 0 ; i < sze1; i++)
{
System.out.print(inArr1[i] + " ");
}
System.out.println( );
for(int i = 0 ; i < sze2; i++)
{
System.out.print(inArr2[i] + " ");
}
// invoking the method mergeTwoSortedArrWithoutExtraSpace() for merging the 
// array without any extra space
obj.mergeTwoSortedArrWithoutExtraSpace(inArr1, inArr2);
System.out.println( );

System.out.println("After merging the sorted arrays, we get: ");
for(int i = 0 ; i < sze1; i++)
{
System.out.print(inArr1[i] + " ");
}
for(int i = 0 ; i < sze2; i++)
{
System.out.print(inArr2[i] + " ");
}

}

}

输出

The input arrays are: 
1 3 7 9 15 20 
2 5 8 11 14 16 18 19 
After merging the sorted arrays, we get: 
1 2 3 5 7 8 9 11 14 15 16 18 19 20

复杂度分析：在该程序中，两个输入数组都只被遍历一次。因此，程序的总时间复杂度为 O(m + n)，其中 'm' 是输入数组 'inArr1[]' 的大小，'n' 是输入数组 'inArr2[]' 的大小。程序的空间复杂度与上一个程序相同。

注意：上述程序对于包含负数的输入数组不起作用。

下一个主题如何在 Java 中调用抽象类的具体方法

Java 中不使用额外空间合并两个排序数组

简单方法：暴力法和排序

算法

另一种方法：使用双指针和排序

算法

另一种方法：使用欧几里得除法引理

算法

注意：上述程序对于包含负数的输入数组不起作用。

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中不使用额外空间合并两个排序数组

简单方法：暴力法和排序

算法

另一种方法：使用双指针和排序

算法

另一种方法：使用欧几里得除法引理

算法

注意：上述程序对于包含负数 的输入数组不起作用。

相关帖子

Java Program to Display Odd Numbers From 1 to 100

Java 中的悬空 else 问题

Abstract Method in Java

Time Class Operation in Java

Java 中构造函数和方法的区别

Check if a Tree is Isomorphic or Not in Java?

Java 中函数和方法的区别

Java 中的 XOR 操作

PMD 是什么

Java 中 Fork/Join 框架和 ExecutorService 的区别

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器

注意：上述程序对于包含负数的输入数组不起作用。