数据结构与算法学习(day4)——解决实际问题

前言

  1. 在本章的学习此前,需要复习前三章的内容,每个算法都动手敲一遍解题。宁愿学慢一点,也要对每个算法掌握基本的理解!

  2. 前面我们学习了简化版桶排序、冒泡排序和快速排序三种算法,今天我们来实践一下前面的三种算法。

  3. 本章的学习目标:

(1)回顾三个算法的基本原理,能够熟悉运用三个算法解决问题

(2)用三种不同算法解决同一个问题

题目

(1)输入有2行,第1行为一个正整数,表示有n个同学参与调查(n<=100)。第2行有n个用空格隔开的正整数,为每本图书的ISBN号(假设图书的ISBN号在1~1000)。

(2)输出也是2行。第1行为一个正整数k,表示需要买多少本书。第2行为k个用空格隔开的正整数,为从小到大已排好序的需要购买的图书的ISBN号(去重)。

例如输入:

10
20 40 32 67 40 20 89 300 400 15

则输出:

8
15 20 32 40 67 89 300 400

(3)最后,程序运行的时间限制为1s。

分析题目

我们要实现的要求有:

  1. 对数据按从小到大顺序排列
  2. 去重

方法一

我想到的第一个方法就是用简化版桶排序。

程序如下:

#include <stdio.h>
int book[1001], n;
int main()
{int i, j, k=0, t;for (i = 0; i <= 1000; i++)book[i] = 0;scanf("%d",&n);for (i = 1; i <= n; i++){scanf("%d", &t);book[t]++;if (book[t] == 1){book[t] = 2;k++;}else if (book[t] > 2){book[t] = 2;}}printf("%d\n",k);for (i = 1; i <= 1000; i++)if(book[i]==2)printf("%d ", i);
}

效果如图
在这里插入图片描述

我们来评价一下这个程序,毫无疑问,这个程序比较无脑,不是一个巧妙的处理方式,但是也可以实现题目要求。

  1. 程序运用的方法是比较简单的桶排序
  2. 思路是先排序(排序实际上数组已经排好了),后去重。
  3. 这个方法的时间复杂度就是桶排序的时间复杂度O(N+M)。

方法二

第二种方法也是先排序后去重,排序我们可以使用冒泡排序或者快速排序,这里我们用冒泡排序举例。

#include <stdio.h>
int main()
{int a[1001], i,j, n,t,k = 0;scanf("%d",&n);for (i = 0; i < n; i++)scanf("%d",&a[i]);//开始冒泡排序for (i = 0; i < n - 1; i++){for (j = 0; j < n - i - 1; j++){if (a[j] > a[j + 1])  //按从小到大的顺序排列{t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;}}}for (i = 0; i < n; i++){if (a[i] == a[i - 1])  //计算重复元素的个数k++;}printf("%d\n",n - k);for (i = 0; i < n; i++){if(a[i] != a[i-1])printf("%d ", a[i]);}	return 0;
}

在这里插入图片描述

我们来评价一下这个程序,

  1. 程序运用的方法是比较简单的冒泡排序
  2. 思路是先排序,后去重。
  3. 这个方法的时间复杂度就是桶排序的时间复杂度O(N^2),冒泡排序的时间复杂度在整个程序中是大块,所以其他两个的时间复杂度不计,时间复杂度比较高。
  4. 如果要排序的数字数量增大,大到10万,桶排序要申请更大的数组,不现实,而冒泡排序的时间复杂度高所以耗时不少,这时候就只能用快速排序,如下;
#include <stdio.h>
/*****************
*a[101]用于存放要排序的数组
* n是要排序的个数
*****************/
int a[1001], n;   //全局变量,这两个变量需要在子函数中使用
/*****************
* 函数名:quicksort
* 形参:int left, int right
* 返回值:无
* 作用:快速排序算法
* ****/
void quicksort(int left, int right)  // left一直都是1
{int i, j, t, temp;if (left > right)return;temp = a[left];  //temp中存的就是基准数i = left;j = right;while (i != j)  //相遇后跳出循环{//顺序很重要,要先从右往左找while (a[j] >= temp && i < j)j--;//再从左往右找while (a[i] <= temp && i < j)i++;//交换两个数再数组中的位置if (i < j)   //当哨兵i和哨兵j没有相遇时{t = a[i];a[i] = a[j];a[j] = t;}}//最终将基准数归位//若相遇,一定是在一个小于基准数的数相遇,将相遇时的数作为基准数进行下一轮的“探测”a[left] = a[i];a[i] = temp;quicksort(left,i-1);  //继续处理左边的,这里是一个递归的过程quicksort(i + 1, right);  //继续处理右边的,这里是一个递归的过程
}
int main()
{int i,j,k = 0;scanf("%d", &n);for (i = 1; i <= n; i++)scanf("%d", &a[i]);//开始快速排序quicksort(1, n);  //快速排序调用for (i = 1; i <= n; i++){if (a[i] == a[i - 1])  //计算重复元素的个数k++;}printf("%d\n", n - k);for (i = 1; i <= n; i++){if (a[i] != a[i - 1])printf("%d ", a[i]);}return 0;
}

在这里插入图片描述

(1)我们在写程序的时候,只要不是面试等需要现场手打程序,那我们可以利用之前写好的代码,移植到我们现在的问题上,来解决问题。

(2)所以,平时多储备知识和源码,还是很重要的,平时的积累,要求我们要掌握好知识,否则到移植的时候,半天都移植不成功。

小结

我们来回顾一下三个算法的时间复杂度。

(1)桶排序是最快的,时间复杂度为O(N+M);

(2)冒泡排序是O(N^2)

(3)快速排序是O(NlogN)

下一节,我们将进入栈、队列、链表的学习。

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

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

相关文章

C# OpenVinoSharp PP-TinyPose 人体姿态识别

效果 项目 部分代码 using OpenCvSharp; using OpenCvSharp.Extensions; using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Windows.Forms;name…

机器学习——支持向量机(SVM)

机器学习——支持向量机&#xff08;SVM&#xff09; 文章目录 前言一、SVM算法原理1.1. SVM介绍1.2. 核函数&#xff08;Kernel&#xff09;介绍1.3. 算法和核函数的选择1.4. 算法步骤1.5. 分类和回归的选择 二、代码实现&#xff08;SVM&#xff09;1. SVR&#xff08;回归&a…

【矩阵分解】PCA - 主成分分析中的数学原理

前言 本文主要对PCA主成分分析中的数学原理进行介绍&#xff0c;将不涉及或很少涉及代码实现或应用&#xff0c;阅读前请确保已了解基本的机器学习相关知识。 文章概述 PCA主成分分析属于矩阵分解算法中的入门算法&#xff0c;通过分解特征矩阵来实现降维。 本文主要内容&a…

硬件学习件Cadence day13 PCB设计中一些设置, 铜皮到钻孔的距离设置, 差分线的设置,板层信息表

1. 设置铺铜中铜皮到钻口&#xff0c;连线的距离。 1. 打开设置界面 2. 设计界面 调整到 铜皮设置界面 2. 高速线的设置 &#xff08;差分对传输线的设置&#xff09; 1. 打开设置界面 2. 来到 差分线设置界面 3. 把界面往右看&#xff0c; 设置差分线的之间距离&#xff0c;…

(二十四)大数据实战——Flume数据流监控之Ganglia的安装与部署

前言 本节内容我们主要介绍一下Flume数据流的监控工具Ganglia。Ganglia是一个开源的分布式系统性能监控工具。它被设计用于监视大规模的计算机群集&#xff08;包括集群、网格和云环境&#xff09;&#xff0c;以便收集和展示系统和应用程序的性能数据。Ganglia 可以轻松地扩展…

【多线程】线程安全 问题

线程安全 问题 一. 线程不安全的典型例子二. 线程安全的概念三. 线程不安全的原因1. 线程调度的抢占式执行2. 修改共享数据3. 原子性4. 内存可见性5. 指令重排序 一. 线程不安全的典型例子 class ThreadDemo {static class Counter {public int count 0;void increase() {cou…

3D点云测量:计算三个平面的交点

文章目录 0. 测试效果1. 基本内容文章目录:3D视觉测量目录0. 测试效果 1. 基本内容 计算三个平面的交点需要找到满足所有三个平面方程的点。三个平面通常由它们的法向量和通过它们的点(或参数形式的方程)来定义。以下是计算三个平面的交点的一般步骤: 假设有三个平面,分别…

MyBatis-Plus排除不必要的字段

查询学生信息排除年龄列表 &#x1f4da;&#x1f50d; 使用MyBatis-Plus排除某些字段。如果你想要进行查询&#xff0c;但又不需要包含某些字段&#xff0c;那么这个功能将非常适合你。&#x1f50d;&#x1f393;&#x1f4dd; 1. 学生信息查询-排除年龄列表 在使用 MyBat…

【Cisco Packet Tracer】管理方式,命令,接口trunk,VLAN

&#x1f490; &#x1f338; &#x1f337; &#x1f340; &#x1f339; &#x1f33b; &#x1f33a; &#x1f341; &#x1f343; &#x1f342; &#x1f33f; &#x1f344;&#x1f35d; &#x1f35b; &#x1f364; &#x1f4c3;个人主页 &#xff1a;阿然成长日记 …

【Redis】为什么要学 Redis

文章目录 前言一、Redis 为什么快二、Redis 的特性2.1 将数据储存到内存中2.2 可编程性2.3 可扩展性2.4 持久性2.5 支持集群2.6 高可用性 三、Redis 的应用场景四、不能使用 Redis 的场景 前言 关于为什么要学 Redis 这个问题&#xff0c;一个字就可以回答&#xff0c;那就是&…

Vue3+Ts+Vite项目(第一篇)——使用Vite创建Vue3项目

概述 保姆级详解&#xff0c;带你使用 Vite 创建 Vue3 项目&#xff0c;全程cv即可 文章目录 概述一、 安装 Vite二、 创建项目2.1 运行上述命令后&#xff0c;会让我们输入项目名称。可以写一个 vue3-study2.2 选择项目模板&#xff0c;此处选择 Vue&#xff0c;然后回车确定…

mysql课堂笔记 mac

目录 启动mac上的mysql 进入mysql mac windows 创建数据库 创建表 修改字段数据类型 修改字段名 增加字段 删除字段 启动mac上的mysql sudo /usr/local/mysql/support-files/mysql.server start 直接输入你的开机密码即可。 编辑 进入mysql mac sudo /usr/local…

深入浅出AXI协议(6)——传输属性

一、前言 在之前的文章中&#xff0c;我们介绍的主要内容是AXI协议的数据读写结构和读写响应结构&#xff0c;主要讲述了当遇到各种特殊情况时,AXI如何完成数据的读写操作&#xff0c;最后介绍了读写响应的4种类型。 在本文中&#xff0c;我们将介绍AXI协议的传输属性。 二、传…

【C++】day3学习成果:类

1.自行封装一个栈的类&#xff0c;包含私有成员属性&#xff1a;栈的数组、记录栈顶的变量 成员函数完成&#xff1a;构造函数、析构函数、拷贝构造函数、入栈、出栈、清空栈、判空、判满、获取栈顶元素、求栈的大小 头文件stack.h: #ifndef STACK_H #define STACK_H#include …

Linux常见指令

目录 前言 一、Linux下的基本指令 01. ls 指令 02. pwd 指令 03. cd 指令 04. touch 指令 05. mkdir 指令&#xff08;重要&#xff09; 06. rmdir 指令 && rm 指令&#xff08;重要&#xff09; 07. man 指令&#xff08;重要&#xff09; extra nano 08. cp 指…

并发聊天服务器编写

并发聊天服务器 package mainimport ("fmt""net""strings""time" )// 结构体 type Client struct {C chan string //用户发送数据的管道Name string //用户名Addr string //网络地址 }// 保存在线用户 cliAddr -->cli…

UNIX网络编程卷一 学习笔记 第三十一章 流

在大多数源自SVR 4的内核中&#xff0c;X/Open传输接口&#xff08;X/Open Transport Interface&#xff0c;XTI&#xff0c;是独立于套接字API的另一个网络编程API&#xff09;和网络协议通常就像终端IO系统那样也使用流系统&#xff08;STREAMS system&#xff09;实现。 我…

Selenium 隐藏浏览器指纹特征的几种方式

我们使用 Selenium 对网页进行爬虫时&#xff0c;如果不做任何处理直接进行爬取&#xff0c;会导致很多特征是暴露的 对一些做了反爬的网站&#xff0c;做了特征检测&#xff0c;用来阻止一些恶意爬虫 本篇文章将介绍几种常用的隐藏浏览器指纹特征的方式 1. 直接爬取 目标对…

基于微服务+Java+Spring Cloud +UniApp +MySql开发的智慧工地源码(物联网、人工智能、AI识别、危大工程)

智慧工地系统利用物联网、人工智能、云计算、大数据、移动互联网等新一代信息技术&#xff0c;通过工地中台、三维建模服务、视频AI分析服务等技术支撑&#xff0c;实现智慧工地高精度动态仿真&#xff0c;趋势分析、预测、模拟&#xff0c;建设智能化、标准化的智慧工地综合业…

vue3+ts项目打包后的本地访问

注意&#xff1a;打包之后不可直接点击html访问&#xff0c;需要给项目安装本地服务&#xff01; 1、安装servenpm i -g serve 2、打包项目npm run build 生成dist文件夹 3、本地访问serve dist 运行service dist之后的控制台 可复制下方的地址运行打包后的项目&#xff0c;运行…