除自身以外数组的乘积、找到所有数组中消失的数字、两数之和
文章目录
- 前言
- 1、除自身以外数组的乘积
- 2、找到所有数组中消失的数字
- 3、两数之和
前言
1、除自身以外数组的乘；
2、找到所有数组中消失的数字；
3、两数之和；
1、除自身以外数组的乘积
题目：
题目链接：
首先题目很简单，就是除了本身以外，其它所有元素的乘积；如果能用除法的话，我们就能很简单的解决这道题，但是现在难点是题目要求我们不准使用除法，这可就难为我们了，题目难度一下就上来了；
既然不能用除法，我们能用乘法啊，我们可以这样想，我们将数组分为两个数组，以每个数组元素为界：
但是这只是计算了一部分，并没有完全计算出结果，我们还需要计算一下右边所有元素的乘积，最终与左边所有元素的乘积对应乘起来就行了；
如何计算右边所有元素乘积，与计算左边一模一样；
接下来我们实例化模拟一下过程：
单次计算左边：
单次计算右边：
时间复杂度：O（N）
空间复杂度：O（N）
代码实现：
int* productExceptSelf(int* nums, int numsSize, int* returnSize){
int *tmp=(int*)malloc(sizeof(int)*numsSize);
int mid=0;
int ret=0;
for(mid=0;mid<numsSize;mid++)
{
if(mid==0)
ret=1;
else
ret=ret*nums[mid-1];
tmp[mid]=ret;
}
for(mid=mid-1;mid>=0;mid--)
{
if(mid==numsSize-1)
ret=1;
else
ret*=nums[mid+1];
tmp[mid]=tmp[mid]*ret;
}
*returnSize=numsSize;
return tmp;
}
2、找到所有数组中消失的数字
题目：
题目链接
分析：找出消失的数字？我们只需要开辟一个与原数组一样大的空间，并且初始化为0，然后对号入座即可，其中位置元素为0的位置表示没有被填充的（也就是消失的数字），位置元素不为0的位置，表示该位置所对应的数字存在；我们最终只需统计一下元素为0都位置，就可推出消失的元素了；
时间复杂度：O（N）
空间复杂度：O（N）
代码实现：
int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize){
int*ret=(int*)malloc(sizeof(int)*numsSize);
int*tmp=(int*)calloc(numsSize,sizeof(int));
for(int index=0;index<numsSize;index++)
{
tmp[nums[index]-1]=nums[index];
}
*returnSize=0;
for(int i=0;i<numsSize;i++)
{
if(!tmp[i])
ret[(*returnSize)++]=i+1;
}
free(tmp);
tmp=NULL;
return ret;
}
法二：
我们对于上面这个算法能不能再优化一下，时间复杂度就没法优化了，看看能不能使用原地算法；
使代码再空间上更进一步优化；首先我们可以优化一下标记的方法；我们知道，再特定下标上是对应特定的元素的，根据这个，我们就对数组进行遍历，我们没遍历一个元素，就找到该元素应该对应下标，然后把该位置元素改为负数，以此来标记，该位置所对应的元素是存在的，最终我们只需再次遍历原数组，找出下标所对应元素不为负数的即可：（按照正常次序来排，3对应的下标为2、9对应的下标为8、2对应的下标为1……
公式：元素=index+1）
时间复杂度：O（N）
空间复杂度：不算返回的空间大小，O（1）
代码实现：
int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize){
int *ret=(int *)malloc(sizeof(int)*numsSize);
int index=0;
for(index=0;index<numsSize;index++)
{
if(nums[abs(nums[index])-1]>0)
nums[abs(nums[index])-1]*=-1;
}
*returnSize=0;
for(int i=0;i<numsSize;i++)
{
if(nums[i]>0)
ret[(*returnSize)++]=i+1;
}
return ret;
}
3、两数之和
题目：
题目链接：
我们可以看到官方将该题标为简单，但是该题确一点也不简单；
我们可看到评论区一篇“惨状”，这足以说明该题的“杀伤力”，博主当时也是暴力破解才勉强通过该题的，直到现在，博主才实现了对于时间上的“一点点优化”，但是却是浪费了空间；我相信随着越往深入学习，我们将会有更优的方法来解决该问题！
博主的辛酸泪😭😭😭：
首先我们来看看暴力破解法：
代码实现：
时间复杂度：O（n^2）
空间复杂度：O（1）
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
*returnSize=2;
static int ret[2]={0,0};
ret[0]=0;
ret[1]=0;
for(int i=0;i<numsSize-1;i++)
{
for(int j=i+1;j<numsSize;j++)
{
if(nums[i]+nums[j]==target)
{
ret[0]=i;
ret[1]=j;
goto eg;
}
}
}
eg:
return ret;
}
比较优化的方法，只能说是在时间上做了一部分优化；
首先我们可以开辟一块与原数组一模一样大的空间，我们在对开辟好的这块空间进行（升序，利用库函数qsort）排序,然后呢我们将下标为0的位置的数一直作为我们的一个加数，剩余的数组成一个新的数组，然后我们只要在该数组找到新的加数，就可以（利用二分查找），最终我们一定会找到该加数（题目保证），我们最终再去原数组寻找找到加数的下标就可以了；
时间复杂度：
1、利用qsort排序O (nlog n)
2、二分查找一次log (N-1),最N次，故 O（n*log n）
3、最后遍历找下标O（N）
总的时间复杂度：O（2nlogn+n）
空间复杂度：O（N）
代码实现：
int cmp(const void * p1,const void * p2)
{
return *(int*)p1-*(int*)p2;
}
bool Two_points(int* a, int left, int right, int key, int* ret)
{
int mid = 0;
while (left <= right)
{
mid = (left + right) / 2;
if (a[mid] > key)
right = mid - 1;
else if (a[mid] < key)
left = mid + 1;
else
{
*ret = key;
return true;
}
}
return false;
}
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
*returnSize = 2;
int* tmp = (int*)malloc(sizeof(int) * 2);//结果数组
int* arr = (int*)malloc(sizeof(int) * numsSize);//辅助数组
int k = 0;
for (k = 0; k < numsSize; k++)//空间换时间//拷贝数组
arr[k] = nums[k];
qsort(arr, numsSize, 4, cmp);//排序
int key1 = 0;//记录加数1
int key2 = 0;//记录加数2
int left = 1;
int right = numsSize - 1;
for (int i = 0; i < numsSize; i++)
{
if (i)//如果不是下标为0的元素，就与下标为0的元素交换
{
int tmp = arr[0];
arr[0] = arr[i];
arr[i] = tmp;
}
key1 = target - arr[0];
if (Two_points(arr, left, right, key1, &key2))//判断是否找到到另一个加数
break;
}
int j = 0;
for (int i = 0; i < numsSize; i++)//寻找加数所对应的下标
{
if (j < 2 && nums[i] == (key2))
{
tmp[j++] = i;
}
else if (j < 2 && nums[i] == arr[0] )
tmp[j++] = i;
if (j >= 2)
break;
}
free(arr);//最后必须释放辅助数组
arr = NULL;
return tmp;//返回结果
}
时间得到了明显的改善，但是空间确是花费了不少，但是对于现在来说，空间已经不在是个问题了，只要能使时间得以提升，我们愿意利用空间换取时间；（这并不是最优的解法，但是确实博主目前来说能想到的最优的解法了，相信在以后的学习中，我们能利用更优的解法来解决这道题！！！😁😁😁）