力扣刷题详解(含代码动态展示)

lovevivi

发布于 2022-11-10 14:38:18

4040

发布于 2022-11-10 14:38:18

文章被收录于专栏：萌新的日常

一、448. 找到所有数组中消失的数字

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
示例 1：输入：nums = [4,3,2,7,8,2,3,1] 输出：[5,6] 示例 2：输入：nums = [1,1] 输出：[2]

1.完整过程动态展示

以输入：nums = [4,3,2,7,8,2,3,1] 输出：[5,6] 为例

2.代码实现

int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize) {
    int* ptr = (int*)malloc(sizeof(int) * numsSize);
    int index = 0;
    int noindex = 0;
    while (index < numsSize)
    {
        if (nums[index] == index + 1)//判断是否与下标+1相等
        {
            index++;
        }
        else
        {
            noindex = nums[index] - 1;
            if (nums[noindex] == nums[index])//如果当前下标的数与
            //与对应位置的数相等
            {
                index++;
                continue;
            }
            int tmp = nums[noindex];//不相等就交换
            nums[noindex] = nums[index];
            nums[index] = tmp;
        }
    }
    int i = 0;
    int n = 0;
    for (i = 0; i < numsSize; i++)
    {
      if (nums[i] != i + 1)
        {
            ptr[n] = i + 1;
            n++;
        }
    }
    *returnSize = n;
    return ptr;
}

3.思路分析

本题说明了所有值都在[1,n]的范围内，所以可以得到

2.首先判断下标所对应的数是否等于下标+1 若等于，则index++，

若不等于则将此时下标对应的数-1看作另一个的下标 比较两个数，若相等，则index++

若不相等则交换

二、238. 除自身以外数组的乘积

给你一个整数数组 nums，返回数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
示例 1: 输入: nums = [1,2,3,4] 输出: [24,12,8,6] 示例 2: 输入: nums = [-1,1,0,-3,3] 输出: [0,0,9,0,0]

1.代码实现

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* productExceptSelf(int* nums, int numsSize, int* returnSize){
    int i=0;
    int*ptr=(int*)malloc(sizeof(int)*(numsSize));
    int left[numsSize];
    int right[numsSize];
    left[0]=1;//默认左缀之和的第一个数为1
    for(i=1;i<numsSize;i++)//左缀之和
    {
        left[i]=left[i-1]*nums[i-1];
    }
    right[numsSize-1]=1;//默认右缀之和的右边第一个数为1
    for(i=numsSize-2;i>=0;i--)//右缀之和
    {
        right[i]=right[i+1]*nums[i+1];
    }
    int index=0;
    for(i=0;i<numsSize;i++)//将左右缀之和相乘 
    {
        ptr[index]=left[i]*right[i];
        index++;
    }
    *returnSize=index;
    return ptr;

}