当前位置: 首页 > news >正文

【LeetCode】面试题总结 消失的数字 最小k个数

 1.消失的数字

两种思路

1.先升序排序,再遍历并且让后一项与前一项比较

2.转化为数学问题求等差数列前n项和 (n的大小为数组的长度),将根据公式求得的应有的和数与数组中实际的和作差


import java.util.*;
class Solution {public int missingNumber(int[] nums) {// 第一种/*Arrays.sort(nums);int len = nums.length;int val = 0;for(int i=0;i<len-1;i++) {if(nums[i+1]!=nums[i]+1) {val = nums[i]+1;break;}}if(val==0) {if(nums[nums.length-1]==nums.length){return 0;}return nums[nums.length-1]+1;}return val;*///第二种int n = nums.length;int sum1 = (n + n*n)/2;int sum2 = 0;for(int i:nums) {sum2 = sum2+i;}return sum1-sum2;}
}

2.最小K个数

优先级队列(默认情况是小根堆) + 比较器改变大小根堆 

第一种 :全部入优先级队列。

第二种 :先只进入k个数,再依次比较,小的加入,大的删除 这样队列中就一直只有k个元素,节省空间,时间。

总结

找第K大的元素  返回小根堆的根节点的值
找第K小的元素,返回大根堆的节点的值

 

 

import java.util.*;
class IntCmp implements Comparator<Integer>{@Overridepublic int compare(Integer o1, Integer o2) {return o2-o1;}
}
class Solution {public int[] smallestK(int[] arr, int k) {/*  第一种 数组中的数全部入优先级队列int[] ret = new int[k];if(arr.length==0) return ret;PriorityQueue<Integer> queue = new PriorityQueue<>(arr.length);for(int i = 0;i<arr.length;i++) {queue.offer(arr[i]);}for(int j = 0;j<k;j++) {ret[j] = queue.poll();} return ret;*//* 第二种 先只进入k个数,再依次比较,小的加入,大的删除 这样队列中就一直只有k个元素*/  //建立大根堆 使用比较器int[] ret = new int[k];if(arr.length==0 || k<=0) return ret;PriorityQueue<Integer> queue = new PriorityQueue<>(new IntCmp());for(int i=0;i<k;i++) {queue.offer(arr[i]);}for(int j=k;j<arr.length;j++) {int top = queue.peek();if(arr[j] < top) {queue.poll();queue.offer(arr[j]);}}for(int i = 0;i<k;i++) {ret[i] = queue.poll();}return ret;/* 找第K大的元素  返回小根堆的根节点的值找第K小的元素,返回大根堆的节点的值*/ }
}

相关文章:

【LeetCode】面试题总结 消失的数字 最小k个数

1.消失的数字 两种思路 1.先升序排序&#xff0c;再遍历并且让后一项与前一项比较 2.转化为数学问题求等差数列前n项和 &#xff08;n的大小为数组的长度&#xff09;&#xff0c;将根据公式求得的应有的和数与数组中实际的和作差 import java.util.*; class Solution {public …...

导入功能importExcel (现成直接用)

1. 实体类字段上加 Excel(name "xxx"), 表示要导入的字段 Excel(name "用户名称")private String nickName; 2. controller (post请求) /*** 导入用户数据** param file 文件* param updateSupport 是否更新支持&#xff0c;如果已存在&#xff0c;则进…...

cvc-complex-type.2.4.a: 发现了以元素 ‘base-extension‘ 开头的无效内容。应以 ‘{layoutlib}‘ 之一开头

不能飞的猪只是没用的猪。 —— 宫崎骏 《红猪》 常见的1种case 记录一下&#xff0c;新电脑安装android studio导入公司那些gradle还是5.5左右的工程以后&#xff0c;各种不适应。编译问题出现了。老电脑都是好好的。 cvc-complex-type.2.4.a: 发现了以元素 ‘base-extensi…...

cortex-A7核IIC实验

iic.h&#xff1a; #ifndef __IIC_H__ #define __IIC_H__ #include "stm32mp1xx_gpio.h" #include "stm32mp1xx_rcc.h"/* 通过程序模拟实现I2C总线的时序和协议* GPIOF ---> AHB4* I2C1_SCL ---> PF14* I2C1_SDA ---> PF15** */#define SET_SDA_…...

task.run()和 await task.run() 区别 await 运行机制

Task.Run() 和 await Task.Run() 都涉及异步编程&#xff0c;但它们在使用场景和效果上有一些区别。1. **Task.Run()&#xff1a;**- Task.Run() 是一个用于在后台线程上执行代码块的方法。它将指定的代码块包装在一个新的Task中&#xff0c;并在后台线程上运行。它不会阻塞调用…...

LeetCode面试经典150题(day 2)

26. 删除有序数组中的重复项 难度:简单 给你一个 升序排列 的数组 nums &#xff0c;请你 原地 删除重复出现的元素&#xff0c;使每个元素 只出现一次 &#xff0c;返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。 考虑 nums 的唯…...

阿里云机器学习PAI全新推出特征平台 (Feature Store),助力AI建模场景特征数据高效利用

推荐算法与系统在全球范围内已得到广泛应用&#xff0c;为用户提供了更个性化和智能化的产品推荐体验。在推荐系统领域&#xff0c;AI建模中特征数据的复用、一致性等问题严重影响了建模效率。阿里云机器学习平台 PAI 推出特征平台&#xff08;PAI-FeatureStore&#xff09; 。…...

网络安全工具和资源推荐: 介绍网络安全领域中常用的工具、框架、资源和学习资料

章节1: 前言 随着数字化时代的不断深入&#xff0c;网络安全的重要性愈发凸显。在这个信息爆炸的时代&#xff0c;我们必须保护个人隐私、敏感数据以及网络基础设施免受各种威胁。本文将为您介绍一些网络安全领域中常用的工具、框架、资源和学习资料&#xff0c;帮助您更好地入…...

『C语言入门』探索C语言函数

文章目录 导言一、函数概述定义与作用重要性 二、函数分类库函数自定义函数定义使用好处 三、函数参数实际参数&#xff08;实参&#xff09;形式参数&#xff08;形参&#xff09;内存分配 四、函数调用传值调用传址调用 五、函数嵌套调用与链式访问嵌套调用链式访问 六、函数…...

Django基础3——视图函数

文章目录 一、基本了解1.1 Django内置函数1.2 http请求流程 二、HttpRequest对象&#xff08;接受客户端请求&#xff09;2.1 常用属性2.2 常用方法2.3 服务端接收URL参数2.4 QueryDict对象2.5 案例2.5.1 表单GET提交2.5.2 表单POST提交2.5.3 上传文件 三、HttpResponse对象&am…...

python 基础篇 day 4 选择结构—— if 结构

文章目录 if 基础结构单 if 语句if-else 语句if-elif-else 语句嵌套的 if 语句 if 进阶用法使用比较运算符使用逻辑运算符使用 in 关键字range() 函数使用 is 关键字使用 pass 语句 三目运算符语法例子注意补充举例注意 if 基础结构 单 if 语句 if 条件: 执行条件为真时的代码…...

科技赋能,教育革新——大步迈向体育强国梦

在 "全民健身"、"体育强国建设"战略的推进下&#xff0c;体育考试成绩被纳入重要升学考试且分值不断提高&#xff0c;体育科目的地位逐步上升到前所未有的高度&#xff0c;在此趋势下&#xff0c;体育教学正演变出更多元化、个性化的需求。然而现实中却面临…...

【秋招基础】后端开发——笔面试常见题目

综述&#xff1a; &#x1f49e;目的&#xff1a;本系列是个人整理为了秋招算法的&#xff0c;整理期间苛求每个知识点&#xff0c;平衡理解简易度与深入程度。 &#x1f970;来源&#xff1a;材料主要源于网上知识点进行的&#xff0c;每个代码参考热门博客和GPT3.5&#xff0…...

自定义loadbalance实现feignclient的自定义路由

自定义loadbalance实现feignclient的自定义路由 项目背景 服务A有多个同事同时开发&#xff0c;每个同事都在dev或者test环境发布自己的代码&#xff0c;注册到注册中心有好几个(本文nacos为例)&#xff0c;这时候调用feign可能会导致请求到不同分支的服务上面&#xff0c;会…...

论文笔记:从不平衡数据流中学习的综述: 分类、挑战、实证研究和可重复的实验框架

0 摘要 论文&#xff1a;A survey on learning from imbalanced data streams: taxonomy, challenges, empirical study, and reproducible experimental framework 发表&#xff1a;2023年发表在Machine Learning上。 源代码&#xff1a;https://github.com/canoalberto/imba…...

C#设计模式六大原则之--迪米特法则

设计模式六大原则是单一职责原则、里氏替换原则、依赖倒置原则、接口隔离原则、迪米特法则、开闭原则。它们不是要我们刻板的遵守&#xff0c;而是根据实际需要灵活运用。只要对它们的遵守程度在一个合理的范围内&#xff0c;努为做到一个良好的设计。本文主要介绍一下.NET(C#)…...

一次js请求一般情况下有哪些地方会有缓存处理?

目录 1、DNS缓存 2、CDN缓存 3、浏览器缓存 4、服务器缓存 1、DNS缓存 DNS缓存指DNS返回了正确的IP之后&#xff0c;系统就会将这个结果临时储存起来。并且它会为缓存设定一个失效时间 (例如N小时)&#xff0c;在这N小时之内&#xff0c;当你再次访问这个网站时&#xff0…...

CSDN编程题-每日一练(2023-08-24)

CSDN编程题-每日一练(2023-08-24) 一、题目名称:计算公式二、题目名称:蛇形矩阵三、题目名称:小玉家的电费一、题目名称:计算公式 时间限制:1000ms内存限制:256M 题目描述: 给定整数n。 计算公式: n i-1 ∑ ∑ [gcd(i + j, i - j) = 1] i=1 j=1 输入描述: 输入整数n…...

怎么把PDF转成Word?需要注意什么事项?

PDF是一种常见的文档格式&#xff0c;但是与Word文档不同&#xff0c;PDF文件通常不能直接编辑。如果您想编辑PDF文件中的文本&#xff0c;或者想将PDF文件转换为Word文档&#xff0c;下面我们就来看一看把PDF转成Word有哪些方法和注意事项。 PDF转Word工具 有许多将PDF转换为…...

USACO22OPEN Pair Programming G

P8273 [USACO22OPEN] Pair Programming G 题目大意 一个程序由一系列指令组成&#xff0c;每条指令的类型如下&#xff1a; d \times d d&#xff0c;其中 d d d是一个 [ 0 , 9 ] [0,9] [0,9]范围内的整数 s s s&#xff0c;其中 s s s是一个表示变量名称的字符串&#xff…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...

解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用

在工业制造领域&#xff0c;无损检测&#xff08;NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统&#xff0c;以非接触式光学麦克风技术为核心&#xff0c;打破传统检测瓶颈&#xff0c;为半导体、航空航天、汽车制造等行业提供了高灵敏…...

什么是VR全景技术

VR全景技术&#xff0c;全称为虚拟现实全景技术&#xff0c;是通过计算机图像模拟生成三维空间中的虚拟世界&#xff0c;使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验&#xff0c;结合图文、3D、音视频等多媒体元素…...

聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇

根据 QYResearch 发布的市场报告显示&#xff0c;全球市场规模预计在 2031 年达到 9848 万美元&#xff0c;2025 - 2031 年期间年复合增长率&#xff08;CAGR&#xff09;为 3.7%。在竞争格局上&#xff0c;市场集中度较高&#xff0c;2024 年全球前十强厂商占据约 74.0% 的市场…...