LeetCode 88合并两个有序数组&89格雷编码

叁歲伎倆 2022-12-29 04:42 142阅读 0赞

> **微信搜一搜**：`bigsai` 专注于Java、数据结构与算法，**一起进大厂不迷路！**  
> **算法文章题解全部收录在github仓库[bigsai-algorithm][],求star！**  
> 关注回复**进群**即可加入力扣打卡群，欢迎划水。近期打卡：  
> [Leetcode 76最小覆盖子串&77组合&78子集][Leetcode 76_77_78]  
> [LeetCode 79单词搜索&80删除排序数组中的重复项Ⅱ&81.搜索旋转排序数组Ⅱ][LeetCode 79_80_81.]  
> [LeetCode 86分割链表&87扰乱字符串][LeetCode 86_87]  
> 如有帮助，记得**一键三连**！

## 合并两个有序数组 ##

题目描述

> 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

说明：

> 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。  
> 你可以假设 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数组然后排序。但是这个并不是特别好的方法。

首先，数组是有序的，第一个方式可以借助一个新的数组实现一趟归并的过程。然后将数据挨个复制到num1数组中。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70]  
实现代码为:

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];
    		 }
        }
    }

但这种方法并不是很好，浪费的空间较多，空间怎么复用呢?

*  如果归并直接在sum1数组归并的话那么会出现错误(前面数字可能未来得及处理就被覆盖)。
 *  所以这里可以**从后向前**进行归并啊！后面的区域一定是可以满足使用的。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 1]  
实现代码为：

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];
    		 }
        }
    }

## 格雷编码 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 2]  
**分析**  
本题的话是个思维题，思想上是个贪心的思想，首先我们要分析这个数值上的关系：

*  每次二进制只能有一位的不同。
 *  每个位上有0，1
 *  需要考虑进位问题

如果只有一位，那肯定是0，1没问题，大部分开始从0开始也没问题，问题是我们怎么采取什么样方式或者策略能够让满足每次只有一个数位不同呢？

*  复用以前的不同
 *  迭代

其实这题就是每次需要考虑进位的时候，数值进位的时候前面加个1，然后从最后一个数字到第一个数字叠加到新的集合中，每进一位就要这样迭代一次，所以数据量每次都以二倍形式增加，具体的话通过一张图就能看懂了。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 3]  
这其实就是推导n-1个和n个数集合数字之间的关系。

*  如果n-1位集合里面数字两两相差为1个不同。
 *  那么n位的首先首位为0的就是n-1个数字的序列能保证。
 *  n位首位为1的就是n-1位从后向前迭代相加(首位为1)

所以在具体迭代的时候就是从后向前每个数加2n 放到集合中即可。  
实现代码为：

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:加上2n 并且前面的数这个位为0，所以可以使用位运算`|`操作就是得到相加的结果。并且这里可以根据size规律直接增加，但是为了通俗易懂这里不改了。

## 结语 ##

原创不易，bigsai请你帮两件事帮忙一下:

1.  star支持一下， 您的肯定是我在平台创作的源源动力。
2.  微信搜索「**bigsai**」，关注我的公众号，不仅免费送你电子书，我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。

记得关注、咱们下次再见！

![image-20201114211553660][]

[bigsai-algorithm]: https://github.com/javasmall/bigsai-algorithm
[Leetcode 76_77_78]: https://bigsai.blog.csdn.net/article/details/110682620
[LeetCode 79_80_81.]: https://bigsai.blog.csdn.net/article/details/110734770
[LeetCode 86_87]: https://bigsai.blog.csdn.net/article/details/111356921
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70]: /images/20221120/910eaa49084349038af6d4482119a7fe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 1]: /images/20221120/6fe8aeb56c804eda91080168765225a8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 2]: /images/20221120/16c22d8ab5fa41598e205df787d0cb08.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 3]: /images/20221120/2e16ad08af0245f8b09e19044c4ea7e0.png
[image-20201114211553660]: /images/20221120/754728ba11164e26b107755c8c862506.png