合并两个有序数组
题目描述
说明：
示例：
输入：
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数组中。
实现代码为:
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数组归并的话那么会出现错误(前面数字可能未来得及处理就被覆盖)。
- 所以这里可以从后向前进行归并啊！后面的区域一定是可以满足使用的。
实现代码为：
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];
}
}
}
格雷编码
分析
本题的话是个思维题，思想上是个贪心的思想，首先我们要分析这个数值上的关系：
- 每次二进制只能有一位的不同。
- 每个位上有0，1
- 需要考虑进位问题
如果只有一位，那肯定是0，1没问题，大部分开始从0开始也没问题，问题是我们怎么采取什么样方式或者策略能够让满足每次只有一个数位不同呢？
- 复用以前的不同
- 迭代
其实这题就是每次需要考虑进位的时候，数值进位的时候前面加个1，然后从最后一个数字到第一个数字叠加到新的集合中，每进一位就要这样迭代一次，所以数据量每次都以二倍形式增加，具体的话通过一张图就能看懂了。
这其实就是推导n-1个和n个数集合数字之间的关系。
- 如果n-1位集合里面数字两两相差为1个不同。
- 那么n位的首先首位为0的就是n-1个数字的序列能保证。
- n位首位为1的就是n-1位从后向前迭代相加(首位为1)
所以在具体迭代的时候就是从后向前每个数加2 放到集合中即可。
实现代码为：
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 并且前面的数这个位为0，所以可以使用位运算|操作就是得到相加的结果。并且这里可以根据size规律直接增加，但是为了通俗易懂这里不改了。
结语
原创不易，bigsai请你帮两件事帮忙一下:
-
star支持一下， 您的肯定是我在平台创作的源源动力。
-
微信搜索「bigsai」，关注我的公众号，不仅免费送你电子书，我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。
记得关注、咱们下次再见！
本文同步分享在 博客“Big sai”（CSDN）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。