C语言每日一练------------Day(7)

本专栏为c语言练习专栏,适合刚刚学完c语言的初学者。本专栏每天会不定时更新,通过每天练习,进一步对c语言的重难点知识进行更深入的学习。

今日练习题关键字:两个数组的交集     双指针

在这里插入图片描述

💓博主csdn个人主页:小小unicorn
⏩专栏分类:C语言天天练
🚚代码仓库:小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识

Day1

  • 题目一:
    • 题目描述:
    • 解题思路:
    • 代码实现:
    • 结果情况:
  • 题目二:
    • 题目描述:
    • 解题思路------两个集合:
      • 思路一:
      • 代码实现:
      • 思路二----排序加双指针:
      • 代码实现:
    • 结果情况:
  • 总结:

题目一:

题目描述:

给你一个整数数组 nums ,其中总是存在 唯一的 一个最大整数 。
请你找出数组中的最大元素并检查它是否 至少是数组中每个其他数字的两倍 。如果是,则返回 最大元素的下标 ,否则返回 -1 。

在这里插入图片描述

解题思路:

遍历数组分别找到数组的最大值 m1 和次大值 m2 。如果 m1≥m2×2 成立,则最大值至少是数组其余数字的两倍,此时返回最大值的下标,否则返回 −1-1−1。

为了返回最大值的下标,我们需要在计算最大值的同时记录最大值的下标。

代码实现:

int dominantIndex(int* nums, int numsSize) 
{int m1 = -1, m2 = -1;int index = -1;for (int i = 0; i < numsSize; i++) {if (nums[i] > m1) {m2 = m1;m1 = nums[i];index = i;} else if (nums[i] > m2) {m2 = nums[i];}}return m1 >= m2 * 2 ? index : -1;
}

结果情况:

在这里插入图片描述
符合题目要求,题目得到解决。

题目二:

题目描述:

给定两个数组 nums1 和 nums2 ,返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

在这里插入图片描述

解题思路------两个集合:

思路一:

计算两个数组的交集,直观的方法是遍历数组 nums1,对于其中的每个元素,遍历数组 nums2 判断该元素是否在数组 nums2 中,如果存在,则将该元素添加到返回值。

假设数组 nums1 和 nums2 的长度分别是 m 和 n,则遍历数组 nums1 需要 O(m) 的时间,判断 nums1 中的每个元素是否在数组 nums2 中需要 O(n) 的时间,因此总时间复杂度是 O(mn)

如果使用哈希集合存储元素,则可以在 O(1)的时间内判断一个元素是否在集合中,从而降低时间复杂度

首先使用两个集合分别存储两个数组中的元素,然后遍历较小的集合,判断其中的每个元素是否在另一个集合中,如果元素也在另一个集合中,则将该元素添加到返回值。该方法的时间复杂度可以降低到 O(m+n)

代码实现:

struct unordered_set 
{int key;UT_hash_handle hh;
};struct unordered_set* find(struct unordered_set** hashtable, int ikey) 
{struct unordered_set* tmp;HASH_FIND_INT(*hashtable, &ikey, tmp);return tmp;
}void insert(struct unordered_set** hashtable, int ikey) 
{struct unordered_set* tmp = find(hashtable, ikey);if (tmp != NULL) return;tmp = malloc(sizeof(struct unordered_set));tmp->key = ikey;HASH_ADD_INT(*hashtable, key, tmp);
}int* getIntersection(struct unordered_set** set1, struct unordered_set** set2, int* returnSize) 
{if (HASH_COUNT(*set1) > HASH_COUNT(*set2)) {return getIntersection(set2, set1, returnSize);}int* intersection = malloc(sizeof(int) * (HASH_COUNT(*set1) + HASH_COUNT(*set2)));struct unordered_set *s, *tmp;HASH_ITER(hh, *set1, s, tmp) {if (find(set2, s->key)) {intersection[(*returnSize)++] = s->key;}}return intersection;
}int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) 
{*returnSize = 0;struct unordered_set *set1 = NULL, *set2 = NULL;for (int i = 0; i < nums1Size; i++) {insert(&set1, nums1[i]);}for (int i = 0; i < nums2Size; i++) {insert(&set2, nums2[i]);}return getIntersection(&set1, &set2, returnSize);
}

思路二----排序加双指针:

如果两个数组是有序的,则可以使用双指针的方法得到两个数组的交集。

首先对两个数组进行排序,然后使用两个指针遍历两个数组。可以预见的是加入答案的数组的元素一定是递增的,为了保证加入元素的唯一性,我们需要额外记录变量 pre\textit{pre}pre 表示上一次加入答案数组的元素。

初始时,两个指针分别指向两个数组的头部。

每次比较两个指针指向的两个数组中的数字,如果两个数字不相等,则将指向较小数字的指针右移一位,如果两个数字相等,且该数字不等于 pre\textit{pre}pre ,将该数字添加到答案并更新 pre\textit{pre}pre 变量,同时将两个指针都右移一位。当至少有一个指针超出数组范围时,遍历结束。

代码实现:

int cmp(void* a, void* b) 
{return *(int*)a - *(int*)b;
}int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) 
{qsort(nums1, nums1Size, sizeof(int), cmp);qsort(nums2, nums2Size, sizeof(int), cmp);*returnSize = 0;int index1 = 0, index2 = 0;int* intersection = malloc(sizeof(int) * (nums1Size + nums2Size));while (index1 < nums1Size && index2 < nums2Size) {int num1 = nums1[index1], num2 = nums2[index2];if (num1 == num2) {// 保证加入元素的唯一性if (!(*returnSize) || num1 != intersection[(*returnSize) - 1]) {intersection[(*returnSize)++] = num1;}index1++;index2++;} else if (num1 < num2) {index1++;}else {index2++;}}return intersection;
}

结果情况:

在这里插入图片描述
符合题目要求,问题得到解决。

总结:

文章到这里就要告一段落了,有更好的想法或问题,欢迎评论区留言。
希望今天的练习能对您有所收获,咱们下期见!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/115330.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【MySQL】存储引擎

1.MySQL体系结构 1). 连接层 最上层是一些客户端和链接服务&#xff0c;包含本地 sock 通信和大多数基于客户端 / 服务端工具实现的类似 于TCP/IP的通信。主要完成一些类似于连接处理、授权认证、及相关的安全方案。在该层上引入 了线程池的概念&#xff0c;为通过认证安全接…

Ubuntu 启动出现grub rescue

​ 一&#xff0c;原因 原因&#xff1a;出现 “grub rescue” 错误通常表示您的计算机无法正常引导到操作系统&#xff0c;而是进入了 GRUB&#xff08;Grand Unified Bootloader&#xff09;紧急模式。这可能是由于引导加载程序配置错误、硬盘驱动器损坏或其他引导问题引起…

js定位到元素底部

文字的一行一行添加的&#xff0c;每次添加要滚动条自动定位到元素底部 <div class"An">//要父元素包裹&#xff0c;父元素设置max-height&#xff0c;overflow啥的<div class"friendly_pW"></div></div>//添加文字时找子元素的高…

Windows右键添加用 IDEA 打开

1.安装IDEA时 安装时会有个选项来添加&#xff0c;如下&#xff1a; 勾选即可 2.修改注册表 安装时未勾选&#xff0c;可以把下面代码中程序路径改为自己的&#xff0c;保存为对应的 idea.reg文件&#xff0c;双击即可 Windows Registry Editor Version 5.00[HKEY_CLASSES…

Screaming Frog SEO Spider,为您的网站提供全方位的优化解决方案

Screaming Frog SEO Spider是一款适用于Mac的软件&#xff0c;它可以帮助用户分析网站的优化信息。该软件可以模拟蜘蛛爬行的方式&#xff0c;抓取网站的各种信息&#xff0c;并将这些信息整理成易于理解的报告。这些报告可以帮助用户评估网站的优化情况&#xff0c;发现链接的…

pyqt5-快捷键QShortcut

import sys from PyQt5.QtWidgets import * from PyQt5.QtCore import * from PyQt5.QtGui import *""" 下面示例揭示了&#xff0c;当关键字绑定的控件出现的时候&#xff0c;快捷键才管用&#xff0c; 绑定的控件没有出现的时候快捷键无效 """…

微前沿 | 第1期:强可控视频生成;定制化样本检索器;用脑电重建视觉感知;大模型鲁棒性评测

欢迎阅读我们的新栏目——“微前沿”&#xff01; “微前沿”汇聚了微软亚洲研究院最新的创新成果与科研动态。在这里&#xff0c;你可以快速浏览研究院的亮点资讯&#xff0c;保持对前沿领域的敏锐嗅觉&#xff0c;同时也能找到先进实用的开源工具。 本期内容速览 01. 强可…

Vue2里监听localstorage里值的变化

有的时候,我们需要根据本地缓存在localstorage里值的变化做出相应的操作,这就需要我们监听localstorage: 首先,我们在src下的libs文件夹下新建一个stroage.js用于重写setItem事件,当使用setItem的时候,触发,window.dispatchEvent派发事件 const Stroage = {// 重写set…

python基础之miniConda管理器

一、介绍 MiniConda 是一个轻量级的 Conda 版本&#xff0c;它是 Conda 的精简版&#xff0c;专注于提供基本的环境管理功能。Conda 是一个流行的开源包管理系统和环境管理器&#xff0c;用于在不同的操作系统上安装、管理和运行软件包。 与完整版的 Anaconda 相比&#xff0c…

安卓版yolo-fastest

安卓版本yolofastest效果测试 安卓配置OPENCV4ANDROID&#xff0c;见我的博客一篇文章opencv4dandroid配置 这个不需要使用JNI&#xff0c;十分简单的配置 说真的&#xff0c;其实只调用OPENCV的函数&#xff0c;自己写的代码不多&#xff0c;使用OPENCV4ANDROID和JNI的时间差…

SPSS教程:如何绘制带误差的折线图

SPSS教程&#xff1a;如何绘制带误差的折线图 1、问题与数据 研究者想研究45-65岁健康男性中&#xff0c;静坐时长和血胆固醇水平的关系&#xff0c;故招募100名研究对象询问其每天静坐时长&#xff08;time&#xff09;&#xff0c;并检测其血液中胆固醇水平&#xff08;cho…

2023开学礼《乡村振兴战略下传统村落文化旅游设计》北农馆藏许少辉八一新书

2023开学礼《乡村振兴战略下传统村落文化旅游设计》北京农学院图书馆许少辉八一新书

ModaHub魔搭社区——决胜大模型时代,算力、网络、向量数据库缺一不可

大模型应用场景日趋多样,需求也随着增加,进而倒逼着多元算力方面的创新,为满足AI工作负载的需求,采用GPU、FPGA、ASIC等加速卡的服务器越来越多。 根据IDC数据统计,2022年,中国加速服务器市场相比2019年增长44.0亿美元,服务器市场增量的一半更是来自加速服务器。 这意味…

已解决 Python FileNotFoundError 的报错问题

本文摘要&#xff1a;本文已解决 Python FileNotFoundError 的相关报错问题&#xff0c;并总结提出了几种可用解决方案。同时结合人工智能GPT排除可能得隐患及错误。 &#x1f60e; 作者介绍&#xff1a;我是程序员洲洲&#xff0c;一个热爱写作的非著名程序员。CSDN全栈优质领…

SQL Server开启变更数据捕获(CDC)

一、CDC简介 变更数据捕获&#xff08;Change Data Capture &#xff0c;简称 CDC&#xff09;&#xff1a;记录 SQL Server 表的插入、更新和删除操作。开启cdc的源表在插入、更新和删除操作时会插入数据到日志表中。cdc通过捕获进程将变更数据捕获到变更表中&#xff0c;通过…

即时物流进入盈利期,为什么说顺丰同城才是“头雁”?

从餐饮店、便利店老板们扮演跑腿角色给顾客送商品算起&#xff0c;即时配送&#xff08;简称“即配”&#xff09;行业跌跌撞撞好几年&#xff0c;规模壮大、秩序提升&#xff0c;但盈亏平衡的及格线&#xff0c;始终让人望洋兴叹。直到这个夏天&#xff0c;平均分终于被拉上去…

服务器部署前后端项目-SQL Father为例

hello~大家好哇&#xff0c;好久没更新博客了。现在来更新一波hhh 现在更新一下部署上的一些东西&#xff0c;因为其实有很多小伙伴跟我之前一样&#xff0c;很多时候只是开发了&#xff0c;本地前后端都能调通&#xff0c;也能用&#xff0c;但是没有部署到服务器试过&#x…

GraphQL渗透测试案例及防御办法

什么是GraphQL GraphQL 是一种 API 查询语言&#xff0c;旨在促进客户端和服务器之间的高效通信。它使用户能够准确指定他们在响应中所需的数据&#xff0c;从而有助于避免有时使用 REST API 看到的大型响应对象和多个调用。 GraphQL 服务定义了一个合约&#xff0c;客户端可…

NPM 常用命令(一)

目录 1、npm 1.1 简介 1.2 依赖性 1.3 安装方式 2、npm access 2.1 命令描述 2.2 详情 3、npm adduser 3.1 描述 4、npm audit 4.1 简介 4.2 审计签名 4.3 操作示例 4.4 配置 audit-level dry-run force json package-lock-only omit foreground-scripts …

如何使用FormKit构建Vue.Js表单

表单是现代网页开发的重要组成部分&#xff0c;创建表单通常是一项耗时且繁琐的任务。这就是FormKit的用武之地&#xff1b;它是一个功能强大的现代表单构建库&#xff0c;旨在帮助开发人员轻松高效地创建表单。 在本文中&#xff0c;我们将探讨使用FormKit的好处&#xff0c;并…