https://zyrastory.com/wp-includes/js/jquery/jquery.min.js
https://zyrastory.com/wp-includes/js/jquery/jquery-migrate.min.js
(function(c,l,a,r,i,t,y){
c[a]=c[a]||function(){(c[a].q=c[a].q||[]).push(arguments)};
t=l.createElement(r);t.async=1;t.src="https://www.clarity.ms/tag/"+i;
y=l.getElementsByTagName(r)[0];y.parentNode.insertBefore(t,y);
})(window, document, "clarity", "script", "btkbh92jgl");
(function(m,e,t,r,i,k,a){m[i]=m[i]||function(){(m[i].a=m[i].a||[]).push(arguments)};
m[i].l=1*new Date();
for (var j = 0; j < document.scripts.length; j++) {if (document.scripts[j].src === r) { return; }}
k=e.createElement(t),a=e.getElementsByTagName(t)[0],k.async=1,k.src=r,a.parentNode.insertBefore(k,a)})
(window, document, "script", "https://mc.yandex.ru/metrika/tag.js", "ym");ym(93103491, "init", {
clickmap:true,
trackLinks:true,
accurateTrackBounce:true
});
(function(c,l,a,r,i,t,y){
c[a]=c[a]||function(){(c[a].q=c[a].q||[]).push(arguments)};t=l.createElement(r);t.async=1;
t.src="https://www.clarity.ms/tag/"+i+"?ref=wordpress";y=l.getElementsByTagName(r)[0];y.parentNode.insertBefore(t,y);
})(window, document, "clarity", "script", "btkbh92jgl");
Skip to content
Post Views: 2,802
LeetCode ProblemYou are given two integer arrays nums1 and nums2 , sorted in non-decreasing order , and two integers m and n , representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order .
The final sorted array should not be returned by the function, but instead be stored inside the array nums1 . To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n .
Follow up: Can you come up with an algorithm that runs in O(m + n) time?
Solution Please be adviced that the problem’s description- “The final sorted array should not be returned by the function, but instead be stored inside the array nums1″
C# Solution Solution1
public class Solution {
public void Merge(int[] nums1, int m, int[] nums2, int n) {
int cnt = 0;
for(int i = m;i<nums1.Length;i++)
{
nums1[i] = nums2[cnt];
cnt++;
}
Array.Sort(nums1);
}
}
The time complexity should be : m-n times + Array.Sort ( based on Quicksort ) ➡ O(n)+O(n log n)
But look at the follow up : “Can you come up with an algorithm that runs in O(m + n) time?”
Maybe we should try another way?
⭐Solution2 (Recommend – two pointer solution)
public class Solution {
public void Merge(int[] nums1, int m, int[] nums2, int n) {
int index = m+n-1; //last index
while(n>0)
{
if(m>0 && nums1[m-1]>nums2[n-1])
{
nums1[index] = nums1[m-1];
m--;
}
else
{
nums1[index] = nums2[n-1];
n--;
}
index --;
}
}
}
What we want to do is combine nums2 n element with nums1 m element to original nums1.
So if we want to combine and sort together, we need to compare the element of two array in iteration.
Time Complexity : O(m + n)
Java Solution Solution1
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int cnt = 0;
for(int i = m;i<nums1.length;i++)
{
nums1[i] = nums2[cnt];
cnt++;
}
Arrays.sort(nums1);
}
}
Runtime : 1ms
⭐Solution2
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int index = m+n-1; //last index
while(n>0)
{
if(m>0 && nums1[m-1]>nums2[n-1])
{
nums1[index] = nums1[m-1];
m--;
}
else
{
nums1[index] = nums2[n-1];
n--;
}
index --;
}
}
}
Runtime : 0ms
Python3 Solution Solution1
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
cnt = 0;
while(m < len(nums1)):
nums1[m] = nums2[cnt];
cnt+=1
m+=1
nums1.sort();
Runtime : 78ms、46ms、54ms ➡ average 59ms
⭐Solution2
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
index = m+n-1
while(n>0):
if(m>0 and nums1[m-1]>nums2[n-1]):
nums1[index] = nums1[m-1];
m-=1;
else:
nums1[index] = nums2[n-1];
n-=1;
index -=1;
Runtime : 59ms、70ms、30ms ➡ average 53ms
JavaScript Solution Solution1
/**
* @param {number[]} nums1
* @param {number} m
* @param {number[]} nums2
* @param {number} n
* @return {void} Do not return anything, modify nums1 in-place instead.
*/
var merge = function(nums1, m, nums2, n) {
var index = m+n-1; //last index
while(n>0)
{
if(m>0 && nums1[m-1]>nums2[n-1])
{
nums1[index] = nums1[m-1];
m--;
}
else
{
nums1[index] = nums2[n-1];
n--;
}
index --;
}
};
Runtime : 97ms、109ms、64ms
Klook.com
Conclusion How to reduce time complexity always is a interesting question of coding.
In this case, you can use a iteration with two pointers to avoid using Array.sort function (List.sort…, etc)
"Eventually, all things merge into one, and a river runs through it."
- Norman Maclean
The problem link : Merge Sorted Array – LeetCode
Reference
Technology Article
Related Post
function closePop(){document.getElementById("headlineatas").style.display = 'none';}
function openPop()
{
if(/Android|webOS|iPhone|iPod|BlackBerry/i.test(navigator.userAgent))
{
return false;
}
var r = Math.random();
if(r>0.7 || r<0.3)
{
document.getElementById("headlineatas").style.display = '';
}
}
(function (d, sc, u) {
var s = d.createElement(sc),
p = d.getElementsByTagName(sc)[0];
s.type = "text/javascript";
s.async = true;
s.src = u;
p.parentNode.insertBefore(s, p);
})(
document,
"script",
"https://affiliate.klook.com/widget/fetch-iframe-init.js"
);
(function (d, sc, u) {
var s = d.createElement(sc),
p = d.getElementsByTagName(sc)[0];
s.type = "text/javascript";
s.async = true;
s.src = u;
p.parentNode.insertBefore(s, p);
})(
document,
"script",
"https://affiliate.klook.com/widget/fetch-iframe-init.js"
);
(adsbygoogle = window.adsbygoogle || []).push({});
(function (d, sc, u) {
var s = d.createElement(sc),
p = d.getElementsByTagName(sc)[0];
s.type = "text/javascript";
s.async = true;
s.src = u;
p.parentNode.insertBefore(s, p);
})(
document,
"script",
"https://affiliate.klook.com/widget/fetch-iframe-init.js"
);
(adsbygoogle = window.adsbygoogle || []).push({});
(adsbygoogle = window.adsbygoogle || []).push({});
(function(d, s, id) {
var js, fjs = d.getElementsByTagName(s)[0];
js = d.createElement(s); js.id = id;
js.src = 'https://connect.facebook.net/en_US/sdk/xfbml.customerchat.js#xfbml=1&version=v6.0&autoLogAppEvents=1'
fjs.parentNode.insertBefore(js, fjs);
}(document, 'script', 'facebook-jssdk'));
function returnDefault(item)
{
item.innerText = "Copy"
item.style.color = "white"
item.style.backgroundColor = "CornflowerBlue";
}
if(/Android|webOS|iPhone|iPod|BlackBerry/i.test(navigator.userAgent) == false) //20221128 手機用戶移除copy功能
{
jQuery('code').each(function () {
var btn = document.createElement("button");
btn.innerHTML = "Copy";
btn.onmousedown = "event.preventDefault();";
btn.setAttribute('class', 'btnC');
btn.onclick = function(){
var k = this.nextSibling;
var textArea = document.createElement("textarea");
textArea.style.position = 'fixed';
textArea.style.top = 0;
textArea.style.left = 0;
textArea.style.width = '2em';
textArea.style.height = '2em';// We don't need padding, reducing the size if it does flash render.
textArea.style.padding = 0;// Clean up any borders.
textArea.style.border = 'none';
textArea.style.outline = 'none';
textArea.style.boxShadow = 'none';// Avoid flash of the white box if rendered for any reason.
textArea.style.background = 'transparent';textArea.value = k.textContent;document.body.appendChild(textArea);
textArea.focus();
textArea.select();var successful = document.execCommand('copy');
var msg = successful ? 'successful' : 'unsuccessful';if(successful)
{
this.focus();
this.style.backgroundColor = "green";
this.innerText = "✔Copied"
//openPop();
setTimeout(( ()=>returnDefault(this)),1850)
}document.body.removeChild(textArea);
};var parent = this.parentNode;
parent.insertBefore(btn, this);
});
}
var eztoc_smooth_local = {"scroll_offset":"30","add_request_uri":""};
https://zyrastory.com/wp-content/plugins/easy-table-of-contents/assets/js/smooth_scroll.min.js
https://zyrastory.com/wp-content/plugins/easy-table-of-contents/vendor/js-cookie/js.cookie.min.js
https://zyrastory.com/wp-content/plugins/easy-table-of-contents/vendor/sticky-kit/jquery.sticky-kit.min.js
var ezTOC = {"smooth_scroll":"1","visibility_hide_by_default":"","scroll_offset":"30","fallbackIcon":"<span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span>","chamomile_theme_is_on":""};
https://zyrastory.com/wp-content/plugins/easy-table-of-contents/assets/js/front.min.js
https://zyrastory.com/wp-content/plugins/highlighting-code-block/assets/js/prism.js
var hcbVars = {"showCopyBtn":"","copyBtnLabel":"Copy code to clipboard"};
https://zyrastory.com/wp-content/plugins/highlighting-code-block/build/js/hcb_script.js
var ct_localizations = {"ajax_url":"https:\/\/zyrastory.com\/wp-admin\/admin-ajax.php","public_url":"https:\/\/zyrastory.com\/wp-content\/themes\/blocksy\/static\/bundle\/","rest_url":"https:\/\/zyrastory.com\/wp-json\/","search_url":"https:\/\/zyrastory.com\/en\/search\/QUERY_STRING\/","show_more_text":"Show more","more_text":"More","search_live_results":"Search results","search_live_no_result":"No results","search_live_one_result":"You got %s result. Please press Tab to select it.","search_live_many_results":"You got %s results. Please press Tab to select one.","expand_submenu":"Expand dropdown menu","collapse_submenu":"Collapse dropdown menu","dynamic_js_chunks":[],"dynamic_styles":{"lazy_load":"https:\/\/zyrastory.com\/wp-content\/themes\/blocksy\/static\/bundle\/non-critical-styles.min.css?ver=2.0.45","search_lazy":"https:\/\/zyrastory.com\/wp-content\/themes\/blocksy\/static\/bundle\/non-critical-search-styles.min.css?ver=2.0.45","back_to_top":"https:\/\/zyrastory.com\/wp-content\/themes\/blocksy\/static\/bundle\/back-to-top.min.css?ver=2.0.45"},"dynamic_styles_selectors":[{"selector":".ct-header-cart, #woo-cart-panel","url":"https:\/\/zyrastory.com\/wp-content\/themes\/blocksy\/static\/bundle\/cart-header-element-lazy.min.css?ver=2.0.45"},{"selector":".flexy","url":"https:\/\/zyrastory.com\/wp-content\/themes\/blocksy\/static\/bundle\/flexy.min.css?ver=2.0.45"}],"lang":"en"};
https://zyrastory.com/wp-content/themes/blocksy/static/bundle/main.js
https://zyrastory.com/wp-includes/js/comment-reply.min.js
(function() {
var expirationDate = new Date();
expirationDate.setTime( expirationDate.getTime() + 31536000 * 1000 );
document.cookie = "pll_language=en; expires=" + expirationDate.toUTCString() + "; path=/; secure; SameSite=Lax";
}());
window.addEventListener("DOMContentLoaded",(e=>{document.querySelectorAll('img[loading="lazy"]').forEach((e=>{e.getBoundingClientRect().top<=window.innerHeight&&(e.loading="eager")}))}));
ai_front = {"insertion_before":"BEFORE","insertion_after":"AFTER","insertion_prepend":"PREPEND CONTENT","insertion_append":"APPEND CONTENT","insertion_replace_content":"REPLACE CONTENT","insertion_replace_element":"REPLACE ELEMENT","visible":"VISIBLE","hidden":"HIDDEN","fallback":"FALLBACK","automatically_placed":"Automatically placed by AdSense Auto ads code","cancel":"Cancel","use":"Use","add":"Add","parent":"Parent","cancel_element_selection":"Cancel element selection","select_parent_element":"Select parent element","css_selector":"CSS selector","use_current_selector":"Use current selector","element":"ELEMENT","path":"PATH","selector":"SELECTOR"};