【LeetCode】移动零&&颜色分类&&有序数组的平方&&有效的山脉数组

简介: 【LeetCode】移动零&&颜色分类&&有序数组的平方&&有效的山脉数组

👉移动零👈


给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。


请注意 ,必须在不复制数组的情况下原地对数组进行操作。

示例 1:


输入: nums = [0,1,0,3,12]

输出: [1,3,12,0,0]



示例 2:


输入: nums = [0]

输出: [0]



提示:


1 <= nums.length <= 104

-231 <= nums[i] <= 231 - 1


进阶:你能尽量减少完成的操作次数吗?


思路一


利用下标 src 找到不为0的元素,再借助中间变量 tmp 将下标为 dst 的元素和 下标为 src 的元素进行交换。遍历数组之后,所有0就被移动到数组的末尾。具体移动操作:当 nums[src] == 0 时,src++;而当 nums[src] != 0 时,进行交换操作后,src++ dst++。


9558816fbad94468a3a4ac2b8c6f98d7.png

void moveZeroes(int* nums, int numsSize)
{
   int dst=0;
   int src=0;
   while(src<numsSize)
   {
       if(nums[src]!=0)
       {
           int tmp=nums[src];
           nums[src]=nums[dst];
           nums[dst]=tmp;
           src++;
           dst++;
       }
       else
           src++;
   }
}

81c483a90cb84daea167ea855226a4e1.png

思路二


利用下标 src 找不是零的元素,将不是零的元素放在下标 dst 的位置上,然后再将数组末尾的元素全部赋值为零。


void moveZeroes(int* nums, int numsSize)
{
    int src = 0;
    int dst = 0;
    while (src < numsSize)
    {
        if (nums[src] != 0)
        {
            nums[dst++] = nums[src++];
        }
        else
        {
            src++;
        }
    }
    //将数组末尾的元素赋值为0
    while (dst < numsSize)
    {
        nums[dst++] = 0;
    }
}

d8406993aa31492eac3e73b7d69ffc71.png



👉调整奇数偶数顺序👈


输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数在数组的前半部分,所有偶数在数组的后半部分。

示例:

输入:nums = [1,2,3,4]

输出:[1,3,2,4]

注:[3,1,2,4] 也是正确的答案之一。


提示:

  • 0 <= nums.length <= 50000
  • 0 <= nums[i] <= 10000


思路:跟移动零的思路一样,只是判断条件变了。

987958335c2448dd8d48297e81a43017.jpg


int* exchange(int* nums, int numsSize, int* returnSize)
{
    int index=0;
    int pos=0;
    while(index<numsSize)
    {
        if(nums[index]%2)
        {
            int tmp=nums[index];
            nums[index]=nums[pos];
            nums[pos]=tmp;
            index++;
            pos++;
        }
        else
            index++;
    }
    *returnSize=numsSize;
    return nums;
}

e2a46bbaf69945bdbfcceaca9fa91890.png


👉颜色分类👈


给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。


我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库的sort函数的情况下解决这个问题。



示例 1:

输入:nums = [2,0,2,1,1,0]

输出:[0,0,1,1,2,2]



示例 2:


输入:nums = [2,0,1]

输出:[0,1,2]



提示:


n == nums.length

1 <= n <= 300

nums[i] 为 0、1 或 2


进阶:


你可以不使用代码库中的排序函数来解决这道题吗?

你能想出一个仅使用常数空间的一趟扫描算法吗?


思路:这道题如果使用 qsort 库函数来解的话,将会显得很简单。在这里,博主就不介绍这种方法了。在这里给大家介绍另一种方法,见下图:

e1e1ef9e84074c18aea211e1945fbfb9.png97e4a91a66604058beb6304a8c9a2876.png

void sortColors(int* nums, int numsSize)
{
    int left = 0;
    int right = numsSize - 1;
    int src = 0;
    while (src <= right)
    {
        if (nums[src] < 1)
        {
            int tmp = nums[src];
            nums[src] = nums[left];
            nums[left] = tmp;
            left++;
            src++;
        }
        else if (nums[src] == 1)
            src++;
        else
        {
            int tmp = nums[src];
            nums[src] = nums[right];
            nums[right] = tmp;
            right--;
        }
    }
}

ec14d0fe92d74e91b40038ff865872fa.png


分析:这道题其实推而广之,num的值可以为任意整数。只不过这道题的num值为1。最需要注意的就是,循环条件是src <= left。如果循环条件错了的话,就无法通过测试了。还需要注意的是,nums[src]num 的大小关系不同,对应着不同的情况。


👉有序数组的平方👈


给你一个按非递减顺序 排序的整数数组 nums,返回每个数字的平方组成的新数组,要求也按非递减顺序 排序。


示例 1:

输入:nums = [-4,-1,0,3,10]

输出:[0,1,9,16,100]

解释:

平方后,数组变为 [16,1,0,9,100];排序后,数组变为 [0,1,9,16,100]



示例 2:


输入:nums = [-7,-3,2,3,11]

输出:[4,9,9,49,121]



提示:


1 <= nums.length <= 104

-104 <= nums[i] <= 104 nums 已按 非递减顺序 排序


进阶:


请你设计时间复杂度为 O(n) 的算法解决本问题



思路一


先将数组中的元素先平方,然后再利用快排对数组进行排序。时间复杂度为O(N+N*logN)空间复杂度O(1)


int cmp(int* a, int* b)
{
    return *a - *b;
}
int* sortedSquares(int* nums, int numsSize, int* returnSize) 
{
    int* num = (int*)malloc(sizeof(int) * numsSize);
    for (int i = 0; i < numsSize; i++)
    {
        nums[i] = nums[i] * nums[i];
    }
    qsort(nums, numsSize, sizeof(int), cmp);
    *returnSize = numsSize;
    return nums;
}


601865bd7bf5437ab37e1e6b34f4ac73.png


思路二


数组其实是有序的, 只不过负数平方之后可能成为最大数了。那么数组平方的最大值就在数组的两端,不是最左边就是最右边,不可能是中间。见下图分析:

c1fa824a2ed6448ca33d3ba88bb521b7.png

int* sortedSquares(int* nums, int numsSize, int* returnSize) 
{
    int* num = (int*)malloc(sizeof(int) * numsSize);
    if(num == NULL)
    {
        *returnSize = 0;
        return num; 
    }
    int left = 0;
    int right = numsSize - 1;
    int index = numsSize - 1;
    while (left <= right)
    {
        if ((nums[left] * nums[left]) > (nums[right] * nums[right]))
        {
            num[index--] = nums[left] * nums[left];
            left++;
        }
        else
        {
            num[index--] = nums[right] * nums[right];
            right--;
        }
    }
    *returnSize = numsSize;
    return num;
}

d45df7122fca4fd5b033855e02aa3f42.png


👉有效的山脉数组👈


给定一个整数数组 arr,如果它是有效的山脉数组就返回 true,否则返回 false。


让我们回顾一下,如果 arr 满足下述条件,那么它是一个山脉数组:

arr.length >= 3

在 0 < i < arr.length - 1 条件下,存在 i 使得:

arr[0] < arr[1]< ... arr[i-1] < arr[i]

arr[i] > arr[i+1] > ... > arr[arr.length - 1]

b96d525544584cf1a74cad331eedd71d.png


           示例 1:

输入:arr = [2,1]

输出:false


示例 2:

输入:arr = [3,5,5]

输出:false


示例 3:

输入:arr = [0,3,2,1]

输出:true


提示:

  • 1 <= arr.length <= 10^4
  • 0 <= arr[i] <= 10^4


思路:判断是山峰,主要就是要严格地保证从左边到中间和从右边到中间是递增的。这样可以使用两个指针,left 和 right,让其按照如下规则移动,如图:

0adbbc63e8ae4060a27de4afc0ad3d91.png


注意:因为left和right是数组下标,移动的过程中注意不要数组越界。如果left或者right没有移动,说明是一个单调递增或者递减的数组,依然不是山峰。

bool validMountainArray(int* arr, int arrSize)
{
    if (arrSize < 3)
        return false;
    int left = 0;
    int right = arrSize - 1;
    //防止越界
    while ((left < arrSize - 1) && (arr[left] < arr[left + 1]))
    {
        left++;
    }
    //防止越界
    while ((right > 0) && (arr[right] < arr[right - 1]))
    {
        right--;
    }
    //如果left或者right在起始位置,说明不是山峰
    if ((left == right) && (left != 0) && (right != arrSize - 1))  return true;
    return false;
}

deb3048fa8b34464bedebb8edfa9b8de.png


👉总结👈


本篇博客主要讲了五道题目,这五道题目或多或少都运用到了双指针的思想。双指针这个思想非常地重要,希望大家能够学会!如果大家觉得有收获的话,可以点个三连支持一下!谢谢大家啦!!!💖💝❣️












相关文章
|
8天前
|
存储 C语言
Leetcode—— 删除排序数组中的重复项——C语言
Leetcode—— 删除排序数组中的重复项——C语言
|
8天前
|
算法 C语言
Leetcode----旋转数组 ------C语言篇
Leetcode----旋转数组 ------C语言篇
|
2天前
|
存储 搜索推荐
题目----力扣--合并两个有序数组
题目----力扣--合并两个有序数组
7 0
|
3天前
|
索引
【力扣刷题】数组实现栈、后缀表达式(逆波兰表达式)求值、中缀表达式转换为后缀表达式(无括号&&有括号)
【力扣刷题】数组实现栈、后缀表达式(逆波兰表达式)求值、中缀表达式转换为后缀表达式(无括号&&有括号)
8 0
|
5天前
DAY-4 | 力扣 - 求自身以外数组的乘积:区间划分,左右累乘,巧求乘积
该文档是关于LeetCode上的一道题目“Product of Array Except Self”的题解。提供了两种解题方法,一是暴力破解,即计算所有数的乘积后再逐个除以当前元素;二是左右累乘法,通过两次遍历数组分别计算左侧和右侧元素的乘积,避免了除法操作。其中,左右累乘法更优,代码实现中展示了这种方法。
13 1
|
7天前
|
存储 算法
【数据结构与算法 | 基础篇】[数组专题]力扣88
【数据结构与算法 | 基础篇】[数组专题]力扣88
|
8天前
|
存储 搜索推荐 C语言
Leetcode—合并两个有序数组—C语言
Leetcode—合并两个有序数组—C语言
|
8天前
力扣2834. 找出美丽数组的最小和
力扣2834. 找出美丽数组的最小和
|
9天前
力扣421. 数组中两个数的最大异或值(字典树)
力扣421. 数组中两个数的最大异或值(字典树)
|
15天前
|
算法
leetcode代码记录(寻找两个正序数组的中位数
leetcode代码记录(寻找两个正序数组的中位数
16 2