数据结构与算法---数组、排序---合并两个有序数组、 颜色分类
合并两个有序数组
题意:
给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出:[1,2,2,3,5,6]
思路1 待验证
给个直观的,设置一个新的数组nums3,长度是nums1的长度,然后nums1和nums2遍历比较,小的放入。放完之后,将nums3数组赋值给nums1即可
但是,如果要求空间复杂度为O(1)呢?
也就是不准建立新的数组
思路2 待验证
那就只能将比较的结果一个一个放入nums1中。
是从前一个一个比较?还是从后一个一个比较?
假设是从前往后比,那么,找出的比较大的元素放置在哪?
明确的是不应该放置在0位置上
那就是,如果nums1[i] > nums2[j] ,两者交换位置,i++;
如果nums1[i] <= nums2[j],j++;
貌似也行
如果是从后往前比较呢?
思路3
设置nums1需要比较的位置为nums1Compare
设置nums1需要插入的位置为nums1Insert
设置nums2需要比较的位置为nums2Compare
如果nums2提前结束,则结束比较,nums1不需要动
如果上面的nums1提前结束,则将nums2赋值到nums1上即可
package 排序_数组;
public class _88_合并两个有序数组 {
public static void main(String[] args)
{
int[] nums1 = {2, 0};
int[] nums2 = {1};
merge(nums1, 1, nums2, 1);
for (int i = 0; i < nums1.length; i++) {
System.out.print(nums1[i] + " ");
}
}
public static void merge(int[] nums1, int m, int[] nums2, int n) {
//从后往前走
//需要三个指针
//指向要插入的地方
int nums1Insert = nums1.length - 1;
//指向要比较的nums1元素
int nums1Compare = m - 1;
//指向要比较的nums2元素
int nums2Compare = n - 1;
//不需要nums1Compare >= 0,因为nums2Compare小于0,说明nums2比较完了,剩余的nums1不用动了
//而nums1Compare < 0,还得将nums2的数据赋值
while(nums2Compare >= 0)
{
if (nums1Compare < 0 || nums1[nums1Compare] < nums2[nums2Compare]) {
nums1[nums1Insert] = nums2[nums2Compare];
nums1Insert--;
nums2Compare--;
}else {
nums1[nums1Insert] = nums1[nums1Compare];
nums1Insert--;
nums1Compare--;
}
}
}
}
颜色分类
75.颜色分类
题目:给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
思路
注意,原地,指的是空间复杂度为O(1)
一般来说,扫描一遍数组就可以解题的,需要借助多个指针。
双指针、三指针
由于题目只有0、1、2三种数字类型
那么,顺序扫描:
如果是0,则放在最前面;
如果是2,则放在最后面;
如果是1,则不动;
假设有一个扫描指针,currentPoint
如果扫描的是0,则需要放在前面的位置,也就是还需要有一个指针指向0需要插入的位置leftPoint
如果扫描的是2,则需要放在后面的位置,也就是还需要有一个指针指向2需要插入的位置rightPoint
如果是0,则currentPoint指向的数值 与 leftPoint指向的数值交换,然后currentPoint++、leftPoint++;
如果是2,则currentPoint指向的数值 与 rightPoint指向的数值交换,rightPoint–,然后再次对currentPoint指向的值进行判断
如果是1,则currentPoint++;
什么时候截止呢?
rightPoint < currentPoint的时候
class Solution {
public void sortColors(int[] nums) {
/**
如果是0,则currentPoint指向的数值 与 leftPoint指向的数值交换,然后currentPoint++、leftPoint++;
如果是2,则currentPoint指向的数值 与 rightPoint指向的数值交换,rightPoint--,然后再次对currentPoint指向的值进行判断
如果是1,则currentPoint++;
*/
int leftPoint = 0;
int rightPoint = nums.length - 1;
int currentPoint = 0;
while(rightPoint >= currentPoint){
if(nums[currentPoint] == 0){
int temp = nums[currentPoint];
nums[currentPoint] = nums[leftPoint];
nums[leftPoint] = temp;
currentPoint++;
leftPoint++;
}else if(nums[currentPoint] == 2){
int temp = nums[currentPoint];
nums[currentPoint] = nums[rightPoint];
nums[rightPoint] = temp;
rightPoint--;
}else if(nums[currentPoint] == 1){
currentPoint++;
}
}
}
}
本文地址:https://blog.csdn.net/IOSSHAN/article/details/109464432
上一篇: Collection集合框架