(文章目录)
一、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;
}
2. 过程
以 1 2 3 4 为例
- 左缀之和
设定一个left数组,用来记录原数组中每个下标所对应的左缀之和 而第一个数不存在左缀的,所以默认为1,所以从左边第二个数开始 left[i]=left[i-1] * nums[i-1]
2.右缀之和
设定一个right数组,用来记录原数组中每个下标所对应的右缀之和 从右向左,右边第一个数不存在右缀之和,所以默认为1 从右边第二个数开始 right[i]=right[i+1] * nums[i+1]
标签:numsSize,index,right,nums,int,力扣,详解,数组,刷题 From: https://blog.51cto.com/u_15787387/5711280
最后分别将left与right每个下标的数相乘 ptr[i]=left[i] * right[i]