<ul id="2uwgk"></ul>

leetcode 88 Merge Sorted Array

bbbbbb 發布于2019-08-15 13:39 / 2258人閱讀

摘要：題目假設數組的長度大于需要排序的元素數量數組的后位為。解法看到這道題時一種常規思路可能是，從頭遍歷兩個數組，將的元素插入到的合適的位置。

題目詳情

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

題目的意思是，輸入兩個已經排好序的數組nums1和nums2，要根據順序把nums2種的元素并入nums1數組中。其中，nums1數組的待排序元素數量為m，nums2數組的待排序元素數量為n。題目假設nums1數組的長度大于需要排序的元素數量（數組的后n位為0）。

解法

看到這道題時一種常規思路可能是，從頭遍歷兩個數組，將nums2的元素插入到nums1的合適的位置。但是在這道題里，數組的插入會導致大量的工作量。

同時我們注意到，nums1數組的后n個位置都是可以被利用的，同時對于這些位置元素的改變并不會影響nums1數組前面待排序的元素。

所以我們從最大的待排序元素進行判斷，將最大的元素賦值給nums1的最后一個元素...以此類推

如果nums1的元素全部排序完畢，nums2的元素還有剩余，那么我們要將nums2數組剩下的元素插入nums1數組中。如果nums2數組先被排序完畢，那么就直接得到了最后的結果。

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        
        int i = m-1;
        int j = n-1;
        int k = m+n-1 ;
        
        while(i >= 0 && j >= 0 ){            
            if(nums1[i] > nums2[j]){
                nums1[k--] = nums1[i--];
            }else{
                nums1[k--] = nums2[j--];
            }
        }
        
        while(j >= 0){
            nums1[k--] = nums2[j--];
        }
        
        
    }

這道題的描述不是很清晰，如果理解了，想法還是比較簡單的～

GPU云服務器云服務器 sorted-array array_merge() array_merge Sorted

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/68227.html

leetcode88 Merge Sorted Array

摘要：題目要求將兩個有序數組合并至其中一個數組并且該新數組仍然有序。所以我們可以換一種思維方式，從大至小遍歷，這樣可以將較大的元素直接填入當前的位置而且不用考慮移動其它的元素。題目要求 Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Note: You...

taohonghui 2019-08-14 18:36 評論0 收藏0
leetcode部分題目答案之JavaScript版

摘要：自己沒事刷的一些的題目，若有更好的解法，希望能夠一起探討項目地址自己沒事刷的一些LeetCode的題目，若有更好的解法，希望能夠一起探討 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...

alphahans 2019-08-21 16:20 評論0 收藏0
leetcode 部分解答索引（持續更新～）

摘要：前言從開始寫相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言從開始寫leetcode相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫～現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理 1~50 1...

leo108 2019-08-15 14:26 評論0 收藏0
[LintCode/LeetCode] Merge Sorted Array

Problem Given two sorted integer arrays A and B, merge B into A as one sorted array. Notice You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements ...

summerpxy 2019-08-14 15:41 評論0 收藏0
[Leetcode] Merge Sorted Array 合并數組

摘要：但是如果我們從后往前，合并到第一個數組的最后，則不用位移。注意將和都先減，用和來代表下標，避免兩個數組為空時拋出空指針異常。 Merge Sorted Array 最新更新請見：https://yanjia.me/zh/2019/02/... Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1...

quietin 2019-08-14 12:26 評論0 收藏0