您好,登錄后才能下訂單哦!
這篇文章主要介紹了C++怎么實(shí)現(xiàn)混合插入有序數(shù)組的相關(guān)知識(shí),內(nèi)容詳細(xì)易懂,操作簡(jiǎn)單快捷,具有一定借鑒價(jià)值,相信大家閱讀完這篇C++怎么實(shí)現(xiàn)混合插入有序數(shù)組文章都會(huì)有所收獲,下面我們一起來看看吧。
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
The number of elements initialized in nums1and nums2 are m and n respectively.
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.
Example:
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3Output: [1,2,2,3,5,6]
混合插入有序數(shù)組,由于兩個(gè)數(shù)組都是有序的,所有只要按順序比較大小即可。題目中說了 nums1 數(shù)組有足夠大的空間,說明不用 resize 數(shù)組,又給了m和n,那就知道了混合之后的數(shù)組的大小,這樣就從 nums1 和 nums2 數(shù)組的末尾開始一個(gè)一個(gè)比較,把較大的數(shù),按順序從后往前加入混合之后的數(shù)組末尾。需要三個(gè)變量 i,j,k,分別指向 nums1,nums2,和混合數(shù)組的末尾。進(jìn)行 while 循環(huán),如果i和j都大于0,再看如果 nums1[i] > nums2[j],說明要先把 nums1[i] 加入混合數(shù)組的末尾,加入后k和i都要自減1;反之就把 nums2[j] 加入混合數(shù)組的末尾,加入后k和j都要自減1。循環(huán)結(jié)束后,有可能i或者j還大于等于0,若j大于0,那么還需要繼續(xù)循環(huán),將 nums2 中的數(shù)字繼續(xù)拷入 nums1。若是i大于等于0,那么就不用管,因?yàn)榛旌蠑?shù)組本身就放在 nums1 中,參見代碼如下:
解法一:
class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int i = m - 1, j = n - 1, 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--]; } };
我們還可以寫的更簡(jiǎn)潔一些,將兩個(gè) while 循環(huán)融合到一起,只要加上 i>=0 且 nums1[i] > nums2[j] 的判斷條件,就可以從 nums1 中取數(shù),否則就一直從 nums2 中取數(shù),參見代碼如下:
解法二:
class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int i = m - 1, j = n - 1, k = m + n - 1; while (j >= 0) { nums1[k--] = (i >= 0 && nums1[i] > nums2[j]) ? nums1[i--] : nums2[j--]; } } };
關(guān)于“C++怎么實(shí)現(xiàn)混合插入有序數(shù)組”這篇文章的內(nèi)容就介紹到這里,感謝各位的閱讀!相信大家對(duì)“C++怎么實(shí)現(xiàn)混合插入有序數(shù)組”知識(shí)都有一定的了解,大家如果還想學(xué)習(xí)更多知識(shí),歡迎關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。