基础算法(2):排序(2):计数排序

1.计数排序实现

     计数排序是一个非基于比较的稳定的线性时间的排序算法,而选择排序是基于比较的,计数排序不用,它的实现依靠计数。

     工作原理:使用一个额外的数组,其中第i个位置是待排序数组1中值等于i的元素的个数,任何根据额外数组来将待排序数组的元素排到正确的位置。

          其实就是做了个映射处理,这个思想和哈希表很像,以后会讲到

          很显然,这是牺牲了空间来换取时间,当待排序数组的值很大时,开辟的空间会很大,浪费了很多空间,所以算法本身就有优点有缺点,下面来看具体实现:

void countSort(int* a,int len)
{
  int max=a[0];
  for(int i=0;i<len;i++)//先找到最大值,方便后面开辟空间
  {
    if(a[i]>max)
     {
       max=a[i];
     }
   }
   int range=max+1;
   int* arr=(int*)calloc(range,sizeof(int));//开辟一个额外数组,并初始化为0
   for(int i=0;i<len;i++)
   {
     arr[a[i]]++;//进行映射,这是核心
   }
   int j=0;
   for(int i=0;i<range;i++)
   {
      while(arr[i]--)//将排好序的元素放回数组中
      {
        a[j]=i;
        j++;
      }
   }
    free(arr);
    arr=NULL;

2.计数排序的时间复杂度

      很显然,问题规模为n,只进行了一次循环,没有进行比较,为n次,时间复杂度为O(n),这是很可观的

3.leetcode题目

3.1 找不同

void countingSort(char* s)
{
    int* arr=(int*)calloc(256,sizeof(int));
    for(int i=0;s[i];i++)
    {
        arr[s[i]]++;
    }
     int j=0;
    for(int i=0;i<256;i++)
    {
        while(arr[i]--)
        {
            s[j]=i;
            j++;
        }
    }
      s[j]='\0';
}
char findTheDifference(char* s, char* t) {
    countingSort(s);
    countingSort(t);
     int i=0;
    for(;s[i];i++)
    {
        if(s[i]!=t[i])
        {
            return t[i];
        }
    }
    return t[i];
}

 3.2 既不是最小值也不是最大值

void countingSort(int* a,int len)
{
     int* arr=(int*)calloc(101,sizeof(int));
     for(int i=0;i<len;i++)
     {
          arr[a[i]]++;
     }
     int j=0;
     for(int i=0;i<101;i++)
     {
         while(arr[i]--)
         {
             a[j]=i;
             j++;
         }
     }
     free(arr);
     arr=NULL;
}
int findNonMinOrMax(int* nums, int numsSize){
     countingSort(nums,numsSize);
     for(int i=0;i<numsSize;i++)
     {
         if(nums[i]==nums[0])continue;
         if(nums[i]==nums[numsSize-1])continue;
         return nums[i];
     }
      return -1;
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Ansible介绍与安装

Ansible目前是运维自动化工具中最简单、容易上手的一款优秀软件&#xff0c;能够用来管理各种资源。用户可以使用Ansible自动部署应用程序&#xff0c;以此实现IT基础架构的全面部署。例如&#xff0c;借助于Ansible&#xff0c;我们可以轻松地对服务器进行初始化配置、安全基线…

显示器件是什么

显示器件 电子元器件百科 文章目录 显示器件前言一、显示器件是什么二、显示器件的类别三、显示器件的应用实例四、显示器件的作用原理总结前言 显示器件根据不同的技术原理和应用领域,具有不同的特点和优势,可适用于电子产品、电视、计算机显示器、手持设备、汽车仪表盘等…

产品入门第四讲:Axure动态面板

&#x1f4da;&#x1f4da; &#x1f3c5;我是默&#xff0c;一个在CSDN分享笔记的博主。&#x1f4da;&#x1f4da; ​​​​​ &#x1f31f;在这里&#xff0c;我要推荐给大家我的专栏《Axure》。&#x1f3af;&#x1f3af; &#x1f680;无论你是编程小白&#xff0c;还…

Java刷题篇——合并两个有序数组

1.题目描述 给出一个有序的整数数组A 和有序的整数数组 B&#xff0c;请将数组B合并到数组A中&#xff0c;变成一个有序的升序数组。 数据范围&#xff1a;0 < n,m < 100, |A~i~| < 100, |B~i~| < 100 注意&#xff1a; 保证 A 数组有足够的空间存放 B 数组的元…

(C++)只出现一次的数字I--异或

个人主页&#xff1a;Lei宝啊 愿所有美好如期而遇 力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台备战技术面试&#xff1f;力扣提供海量技术面试资源&#xff0c;帮助你高效提升编程技能&#xff0c;轻松拿下世界 IT 名企 Dream Offer。https://le…

AI:100-基于卷积神经网络的农作物生长状态监测

🚀 本文选自专栏:人工智能领域200例教程专栏 从基础到实践,深入学习。无论你是初学者还是经验丰富的老手,对于本专栏案例和项目实践都有参考学习意义。 ✨✨✨ 每一个案例都附带有在本地跑过的核心代码,详细讲解供大家学习,希望可以帮到大家。欢迎订阅支持,正在不断更新…

Axure的动态面板

目录 动态面板 什么是Auxre动态模板 动态模板的步骤 应用场景 实战案例 轮播图 多功能登录界面 主界面左侧菜单栏 动态面板 什么是Auxre动态模板 动态面板是Axure中的一个重要功能&#xff0c;它允许用户创建可交互的页面&#xff0c;并模拟用户与页面的交互。通过添加元素…

智能指针管理“newed对象”

为什么要有智能指针&#xff1f; 指针智能是管理管理动态内存分配对象的一种机制。它提供了自动管理内存&#xff0c;避免常见内存泄漏和悬空指针。 对于上述Func函数的操作&#xff0c;一不小心就会产生很多问题。 p1 new时候抛异常 什么都不做p2 new时候抛异常 p1需要被清理…

Apache DolphinScheduler 社区荣获 “2023 年度优秀开源技术团队“ 奖项

在开源社区日益繁荣的今天&#xff0c;我们非常荣幸地宣布&#xff1a;Apache DolphinScheduler 社区在 OSCHINA 平台的评选中荣获了“2023 年度优秀开源技术团队”奖项。这一奖项反映了我们社区在过去一年里在内容发表的深度与广度、活动运营影响力以及对开源文化的推广方面所…

每日一题 --- 2477. 到达首都的最少油耗

链式前向星解法 核心点是我dfs两次&#xff0c;第一次是求出每个节点的叶子节点有多少个&#xff1f; 因为我们可以看做从当前节点出发到当前节点的根节点的话&#xff0c;那么需要知道当前节点叶子节点个数&#xff0c;也就是我们让当前节点的叶子结点&#xff08;代表&…

yolov8常用命令

1.运行预测 &#xff08;1&#xff09;运行目标检测模型&#xff1a; yolo predict modelyolov8n.pt sourcebus.jpg &#xff08;2&#xff09;运行目标检测与分割模型 yolo predict modelyolov8n-seg.pt sourcebus.jpg 2.模型训练 复制coco128.yaml更名为myDetect.y…

检测车牌的SIFT特征并匹配

# 代码5-14 检测车牌的SIFT特征并匹配 import cv2img1 cv2.imread(../data/plate.jpg) img2 cv2.imread(../data/car.jpg)sift cv2.SIFT_create() # 利用sift.detectAndCompute()函数找到特征点&#xff0c;计算描述符&#xff1b; kp1, des1 sift.detectAndCompute(img1, …

Unity Sentis首份教程来啦,利用AI模型创建先进功能

Unity 推出的 Sentis&#xff0c;赋予开发者将 AI 模型导入游戏和应用程序中的能力。现在&#xff0c;Sentis 已进入预发布的开放测试阶段&#xff0c;用户可以在所有类型的项目中实现物体识别、语音识别和智能 NPC 等复杂功能。 这些 AI 模型一旦通过 ONNX 文件标准导入&…

地图自定义省市区合并展示数据整合

需求一&#xff1a;将省级地图下的两个市合并成一个区域&#xff0c;中间的分割线隐藏。 1、访问下方地址&#xff0c;搜索并下载省级地图json文件。 地址&#xff1a;https://datav.aliyun.com/portal/school/atlas/area_selector 2、切换到边界生成器&#xff0c;上传刚刚下…

基于Java+SpringBoot+Vue3+Uniapp前后端分离考试学习一体机设计与实现企业级2.01版本(视频讲解,已发布上线)

博主介绍&#xff1a;✌全网粉丝5W&#xff0c;全栈开发工程师&#xff0c;从事多年软件开发&#xff0c;在大厂呆过。持有软件中级、六级等证书。可提供微服务项目搭建与毕业项目实战&#xff0c;博主也曾写过优秀论文&#xff0c;查重率极低&#xff0c;在这方面有丰富的经验…

【经验分享】gemini-pro和gemini-pro-vision使用体验

Gemini Gemini已经对开发者开放了Gemini Pro的使用权限&#xff0c;目前对大家都是免费的&#xff0c;每分钟限制60条&#xff0c;至少这比起CloseAI的每个账户5刀限速1min3条要香的多&#xff0c;目前已于第一时间进行了体验 一句话总结&#xff0c;google很大方&#xff0c;但…

web服务器之——搭建两个基于域名访问的网站

目录 要求&#xff1a; 一、准备工作&#xff1a;web服务器搭建 第一步&#xff1a;挂载 第二步&#xff1a;编辑配置文件 第三步&#xff1a;安装软件包 第四步&#xff1a;启动httpd 查看配置文件&#xff1a; 第五步&#xff1a;设置防火墙状态&#xff1a; 重启服务…

虹科技术 | IO-Link Wireless如何赋能工厂车间迈向无线自动化?

大规模定制、卓越运营和商业智能正在从根本上改变制造业&#xff0c;为了在竞争中立于不败之地&#xff0c;制造商需要更加灵活、通用、可扩展和具有成本效益的机器和生产线。随着制造商向工业 4.0 迈进&#xff0c;更好的适应性、更高的吞吐量和更短的停机时间是他们的共同要求…

【C++】策略模式

目录 一、简介1. 含义2. 特点 二、实现1. 策略接口&#xff08;Strategy Interface&#xff09;2. 具体策略类&#xff08;Concrete Strategies&#xff09;3. 上下文类&#xff08;Context&#xff09;4. 使用策略模式 三、总结如果这篇文章对你有所帮助&#xff0c;渴望获得你…

【Java系列】详解多线程(二)——Thread类及常见方法(下篇)

个人主页&#xff1a;兜里有颗棉花糖 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【Java系列专栏】【JaveEE学习专栏】 本专栏旨在分享学习Java的一点学习心得&#xff0c;欢迎大家在评论区交流讨论&#x1f48c; 目录 一…