使用另一个数组最大化元素的 JavaScript 程序


在本文中,我们将实现一个 JavaScript 程序,使用另一个数组来最大化元素。我们得到了两个数组,并且必须从第二个数组中选择一些元素并替换第一个数组的元素。我们将看到实现将要讨论的概念的完整代码。

问题简介

在这个问题中,我们得到了两个数组,我们必须使第一个数组的所有元素尽可能最大,或者简单地说,我们必须使第一个数组的所有元素的总和最大。我们可以从第二个数组中选择元素,但关键是我们每次只能从第二个数组中选择一个元素,选择后不能再选择。例如 -

我们得到了两个数组 -

Array1: 1 2 3 4 5 
Array2: 5 6 2 1 9

我们可以看到第二个数组中有很多元素大于第一个数组中存在的元素。

我们可以用 9 替换 3,用 6 替换 2,用 5 替换 1。这使得最终数组看起来像这样 -

5 6 9 4 5 

我们将看到两种方法,两种方法都通过对数组进行排序和使用两个指针来实现,但唯一的区别在于我们将在哪里选择指针。

方法

我们已经看到了上面的例子,从中我们可以看出,我们可以用第二个数组中最大的元素替换第一个数组中最小的元素。

  • 步骤 1 - 首先,我们将对两个数组进行升序排序,然后我们将反转第二个数组使其降序排序。

  • 步骤 2 - 我们将维护两个指针,它们将指向两个数组的第一个索引。

  • 步骤 3 - 由于第一个元素指针将指向最小的数字,因此我们可以用第二个数组中最大的数字替换该数字。

  • 步骤 4 - 在每次迭代中,我们将交换两个数组的指针并增加指针。

  • 步骤 5 - 如果第一个数组当前索引的元素变得大于第二个数组的元素,那么我们可以停止后续步骤。

  • 步骤 6 - 最后,我们将打印数组的元素。

示例

Open Compiler
// function to find the maximum array function maximumArray(array1, array2){ var len1 = array1.length var len2 = array2.length // sorting the elements of both arrays array1.sort() array2.sort() // reversing the arrays array1.reverse() array2.reverse() // traversing over the arrays var ptr1 = 0 var ptr2 = 0 var ptr3 = 0 // creating new array to store the answer var ans = new Array(len1); while(ptr3 < len1){ if(ptr2 == len2){ while(ptr3 != len1){ ans[ptr3] = array1[ptr1]; ptr3++; ptr1++; } } else if(array1[ptr1] > array2[ptr2]){ ans[ptr3] = array1[ptr1]; ptr1++; } else { ans[ptr3] = array2[ptr2]; ptr2++; } ptr3++; } console.log("The final array is: ") console.log(ans) } // declaring arrays array1 = [1, 2, 4, 5, 3] array2 = [5, 6, 2, 1, 9] // calling the function maximumArray(array1,array2)

时间和空间复杂度

以上代码的时间复杂度为 O(N*log(N)),其中 N 是给定数组的大小,这里的对数因子是由于我们用来对数组进行排序的排序函数。

我们使用了一个额外的数组来存储元素,这使得空间复杂度为 O(N),但该数组需要存储答案,因此它可能被认为是额外的空间,也可能不被认为是额外的空间。

直接排序方法

在之前的方法中,我们对数组的元素进行了排序,然后我们使用了两个指针的方法,但是有一种直接的方法,我们可以简单地使用它 -

  • 通过使用 new 关键字和 Array 关键字,我们将创建一个新数组,其大小为两个给定数组的总和或长度。

  • 我们将逐个将两个给定数组的所有元素填充到新数组中。

  • 我们将对新创建的数组进行排序,以使元素按升序排列。

  • 所有最大的元素都位于最后,我们可以很容易地获取它们。

示例

Open Compiler
// function to find the maximum array function maximumArray(array1, array2){ var len1 = array1.length var len2 = array2.length var ans = new Array(len1+len2); for(var i = 0; i<len1; i++){ ans[i] = array1[i]; } for(var i = 0; i< len2; i++){ ans[i+len1] = array2[i]; } ans.sort(); for(var i = 0;i<len1;i++){ array1[i] = ans[len2+len1-i-1]; } console.log("The final array is: ") console.log(array1) } // declaring arrays array1 = [1, 2, 4, 5, 3] array2 = [5, 6, 2, 1, 9] // calling the function maximumArray(array1,array2)

时间和空间复杂度

以上代码的时间复杂度为 O(N*log(N)),其中 N 是给定数组的大小,这里的对数因子是由于我们用来对数组进行排序的排序函数。

我们使用了一个额外的数组来存储元素,这使得空间复杂度为 O(N)。

Learn JavaScript in-depth with real-world projects through our JavaScript certification course. Enroll and become a certified expert to boost your career.

结论

在上面的教程中,我们实现了一个 JavaScript 程序,使用另一个数组来最大化元素。我们得到了两个数组,并且必须从第二个数组中选择一些元素并替换第一个数组的元素。我们已经看到了两种方法,两种方法都使用了排序的概念。一种使用两个指针的方法花费 O(N*log(N)) 的时间和 O(1) 的空间,而另一种方法花费相同的时间但 O(N) 的空间。

更新于: 2023-03-30

144 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告