微信搜一搜：bigsai 專注于Java、數(shù)據(jù)結(jié)構(gòu)與算法，一起進大廠不迷路！
算法文章題解全部收錄在github倉庫bigsai-algorithm,求star！
關(guān)注回復(fù)進群即可加入力扣打卡群，歡迎劃水。近期打卡：
Leetcode 76最小覆蓋子串&77組合&78子集
LeetCode 79單詞搜索&80刪除排序數(shù)組中的重復(fù)項Ⅱ&81.搜索旋轉(zhuǎn)排序數(shù)組Ⅱ
LeetCode 86分割鏈表&87擾亂字符串
如有幫助，記得一鍵三連！

合并兩個有序數(shù)組

題目描述

給你兩個有序整數(shù)數(shù)組 nums1 和 nums2，請你將 nums2 合并到 nums1 中，使 nums1 成為一個有序數(shù)組。

說明：

初始化 nums1 和 nums2 的元素數(shù)量分別為 m 和 n 。
你可以假設(shè) nums1 有足夠的空間（空間大小大于或等于 m + n）來保存 nums2 中的元素。

示例：

輸入： nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3輸出：[1,2,2,3,5,6]

提示：

-10^9 <= nums1[i], nums2[i] <= 10^9 nums1.length == m + n nums2.length == n

這題的思路很多，你可以先拼接到num1數(shù)組然后排序。但是這個并不是特別好的方法。

首先，數(shù)組是有序的，第一個方式可以借助一個新的數(shù)組實現(xiàn)一趟歸并的過程。然后將數(shù)據(jù)挨個復(fù)制到num1數(shù)組中。

實現(xiàn)代碼為:

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int index1=0;int index2=0;int a[]=new int[m+n];while (index1<m&&index2<n) {if(nums1[index1]<=nums2[index2]){a[index1+index2]=nums1[index1];index1++;}else {a[index1+index2]=nums2[index2];index2++;}}for(;index1<m;index1++){a[index1+index2]=nums1[index1];}for(;index2<n;index2++){a[index1+index2]=nums2[index2];}for(int i=0;i<m+n;i++){nums1[i]=a[i];}} }

但這種方法并不是很好，浪費的空間較多，空間怎么復(fù)用呢?

• 如果歸并直接在sum1數(shù)組歸并的話那么會出現(xiàn)錯誤(前面數(shù)字可能未來得及處理就被覆蓋)。
• 所以這里可以從后向前進行歸并啊！后面的區(qū)域一定是可以滿足使用的。

實現(xiàn)代碼為：

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int index1=m-1;int index2=n-1;while (index1>=0&&index2>=0) {if(nums1[index1]>=nums2[index2]){nums1[index1+index2+1]=nums1[index1--];}else {nums1[index1+index2+1]=nums2[index2--];}}for(;index2>=0;index2--){nums1[index2]=nums2[index2];}} }

格雷編碼

分析
本題的話是個思維題，思想上是個貪心的思想，首先我們要分析這個數(shù)值上的關(guān)系：

• 每次二進制只能有一位的不同。
• 每個位上有0，1
• 需要考慮進位問題

如果只有一位，那肯定是0，1沒問題，大部分開始從0開始也沒問題，問題是我們怎么采取什么樣方式或者策略能夠讓滿足每次只有一個數(shù)位不同呢？

• 復(fù)用以前的不同
• 迭代

其實這題就是每次需要考慮進位的時候，數(shù)值進位的時候前面加個1，然后從最后一個數(shù)字到第一個數(shù)字疊加到新的集合中，每進一位就要這樣迭代一次，所以數(shù)據(jù)量每次都以二倍形式增加，具體的話通過一張圖就能看懂了。

這其實就是推導(dǎo)n-1個和n個數(shù)集合數(shù)字之間的關(guān)系。

• 如果n-1位集合里面數(shù)字兩兩相差為1個不同。
• 那么n位的首先首位為0的就是n-1個數(shù)字的序列能保證。
• n位首位為1的就是n-1位從后向前迭代相加(首位為1)

所以在具體迭代的時候就是從后向前每個數(shù)加2ⁿ 放到集合中即可。
實現(xiàn)代碼為：

class Solution {public List<Integer> grayCode(int n) {List<Integer>list=new ArrayList<Integer>();list.add(0);int num=1;for(int i=0;i<n;i++){int size=list.size();for(int j=size-1;j>=0;j--){list.add(list.get(j)+num);}num=num<<1; }return list;} }

ps:加上2ⁿ 并且前面的數(shù)這個位為0，所以可以使用位運算|操作就是得到相加的結(jié)果。并且這里可以根據(jù)size規(guī)律直接增加，但是為了通俗易懂這里不改了。

結(jié)語

原創(chuàng)不易，bigsai請你幫兩件事幫忙一下:

star支持一下， 您的肯定是我在平臺創(chuàng)作的源源動力。

微信搜索「bigsai」，關(guān)注我的公眾號，不僅免費送你電子書，我還會第一時間在公眾號分享知識技術(shù)。加我還可拉你進力扣打卡群一起打卡LeetCode。

記得關(guān)注、咱們下次再見！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 88合并两个有序数组89格雷编码的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。