目录
悟已往之不谏,知来者犹可追
创作不易,宝子们!如果这篇文章对你们有帮助的话,别忘了给个免费的赞哟~
1.题目描述
给你一个整数数组 nums ,其中总是存在 唯一的 一个最大整数 。请你找出数组中的最大元素并检查它是否 至
少是数组中每个其他数字的两倍 。如果是,则返回 最大元素的下标 ,否则返回 -1 。
OJ链接【 leetcode 题号:747. 至少是其他数字两倍的最大数】【难度:简单】
示例:
输入:nums = [3,6,1,0]
输出:1
解释:6 是最大的整数,对于数组中的其他整数,6 大于数组中其他元素的两倍。6 的下标是 1 ,所以返回 1 。
输入:nums = [1,2,3,4]
输出:-1
解释:4 没有超过 3 的两倍大,所以返回 -1 。
输入:nums = [1]
输出:0
解释:因为不存在其他数字,所以认为现有数字 1 至少是其他数字的两倍
349. 两个数组的交集 – 力扣(LeetCode)题目链接放这里啦~
2.C语言中的内置排序函数(qsort)
在讲解题目之前我想和宝子们分享一个C语言中的内置排序函数~
举个栗子啦~ /* qsort example */ #include <stdio.h> /* printf */ #include <stdlib.h> /* qsort */ int values[] = { 40, 10, 100, 90, 20, 25 }; int compare (const void * a, const void * b) { return ( *(int*)a - *(int*)b ); } int main () { int n; qsort (values, 6, sizeof(int), compare); for (n=0; n<6; n++) printf ("%d ",values[n]); return 0; }
3.解题思路
3.1 升序
这道题很明显是用哈希数组来做,但如果我们没有学哈希表的话,或者我们是否还有其他的方法来解题呢~
之前我们就知道对于无序的数组,当我们对其进行排序后,问题都会变得更加简单呢~
没有例外,我们现将这俩个数组进行有序化处理
int intCmp (const void * a, const void * b) { return ( *(int*)a - *(int*)b ); } qsort(nums1, nums1Size, sizeof(int), intCmp); qsort(nums2, nums2Size, sizeof(int), intCmp); *returnSize = 0;//要返回数组的大小先初始化为零 int index1 = 0,;//记录数组一的下标 int index2 = 0;//记录数组二的下标 //创建一个最大的数组来存放相同的元素 int* returnNums = malloc(sizeof(int) * (nums1Size + nums2Size));
3.2双指针的移动
然后我们有俩个指针分别指向数组nums1中的第一个元素和nums2的第一个元素~
要求俩个数组的交集,那我们就要找俩个数组当中相同的元素~
所以我们就要一一比较俩个数组中的元素,那我们怎么比较呢~
我们先比较俩个指针指向的第一个元素,如果相同,双指针就同时向后移动,并把相同元素存放到数组returnNums中,如果不相同,则哪个指针指向的元素小,哪个指针就向后移动后继续比较
算法的图示在下面啦~
这部分的代码如下啦~
//两个都小于数组长度才去遍历 while (index1 < nums1Size && index2 < nums2Size) { if (nums1[index1] == nums2[index2]) { returnNums[(*returnSize)++] = nums1[index1]; index1++; index2++; } else if (nums1[index1] < nums2[index2]) index1++; else index2++; }
3.3 保证加入元素的唯一性
注意:我们还要确保加入returnNums中元素的唯一性!
所以我们还要加上一个判断条件~
if(!*(returnSize)||nums1[index1]!=returnNums[*(returnSize)-1]) returnNums[(*returnSize)++] = nums1[index1];
!*(returnSize)表示当(*returnSize)=0(即表示假)把他转换成为真以此来应对当数组中还没有存放元素是的情况
4.leetcode上的完整代码
int intCmp (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize)
{
qsort(nums1, nums1Size, sizeof(int), intCmp);
qsort(nums2, nums2Size, sizeof(int), intCmp);
*returnSize = 0;//要返回数组的大小先初始化为零
int index1 = 0;//记录数组一的下标
int index2 = 0;//记录数组二的下标
//创建一个最大的数组来存放相同的元素
int* returnNums = malloc(sizeof(int) * (nums1Size + nums2Size));
//两个都小于数组长度才去遍历
while (index1 < nums1Size && index2 < nums2Size)
{
if (nums1[index1] == nums2[index2])
{
if(!*(returnSize)||nums1[index1]!=returnNums[*(returnSize)-1])
returnNums[(*returnSize)++] = nums1[index1];
index1++;
index2++;
}
else if (nums1[index1] < nums2[index2])
index1++;
else
index2++;
}
return returnNums;
}
5.完结散花
好了,这期的分享到这里就结束了~
如果这篇博客对你有帮助的话,可以用你们的小手指点一个免费的赞并收藏起来哟~
如果期待博主下期内容的话,可以点点关注,避免找不到我了呢~
我们下期不见不散~~
版权声明:本文为博主作者:秋风起,再归来~原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/2301_80221228/article/details/136081640