OJ刷题：求俩个数组的交集（没学哈希表？快排双指针轻松搞定！）

目录

 

                                            悟已往之不谏，知来者犹可追                                                        

创作不易，宝子们！如果这篇文章对你们有帮助的话，别忘了给个免费的赞哟~ 

 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.完结散花

好了，这期的分享到这里就结束了~

如果这篇博客对你有帮助的话，可以用你们的小手指点一个免费的赞并收藏起来哟~

如果期待博主下期内容的话，可以点点关注，避免找不到我了呢~

我们下期不见不散~~