首页 > 编程语言 >#yyds干货盘点# LeetCode程序员面试金典:数字流的秩

#yyds干货盘点# LeetCode程序员面试金典:数字流的秩

时间:2023-02-18 16:02:11浏览次数:34  
标签:StreamRank yyds int getRankOfNumber list public track 金典 LeetCode

题目:

假设你正在读取一串整数。每隔一段时间,你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。请实现数据结构和算法来支持这些操作,也就是说:

实现 track(int x) 方法,每读入一个数字都会调用该方法;

实现 getRankOfNumber(int x) 方法,返回小于或等于 x 的值的个数。

注意:本题相对原题稍作改动

示例:

输入:

["StreamRank", "getRankOfNumber", "track", "getRankOfNumber"]

[[], [1], [0], [0]]

输出:

[null,0,null,1]

代码实现:

class StreamRank {

public StreamRank() {
list = new ArrayList<>();
}
List<Integer> list;
public void track(int x) {
int i = 0;
int j = list.size()-1;
while(i <= j){
int m = i + (j-i)/2;
if(list.get(m) < x){i = m+1;}
else{j = m-1;}
}// 寻找第一个比它大的数
list.add(i, x);// 在其下标处插入x
}

public int getRankOfNumber(int x) {
int i = 0;
int j = list.size()-1;
while(i <= j){
int m = i + (j-i)/2;
if(list.get(m) > x){j = m-1;}
else{i = m+1;}
}// 寻找最后一个不大于它的数
return j+1;// 下标加1才是元素数目(秩)
}
}

标签:StreamRank,yyds,int,getRankOfNumber,list,public,track,金典,LeetCode
From: https://blog.51cto.com/u_13321676/6065444

相关文章

  • #yyds干货盘点# LeetCode面试题:四数之和
    1.简述:给你一个由n个整数组成的数组 nums,和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a],nums[b],nums[c],nums[d]] (若两个四元......
  • 【算法训练营day46】LeetCode139. 单词拆分 多重背包基础
    LeetCode139.单词拆分题目链接:139.单词拆分独上高楼,望尽天涯路没什么思路。慕然回首,灯火阑珊处挖个坑,二刷的时候填。classSolution{public:boolwordBreak......
  • LeetCode 93_复原 IP 地址
    LeetCode93:复原IP地址题目有效IP地址正好由四个整数(每个整数位于0到255之间组成,且不能含有前导0),整数之间用'.'分隔。例如:"0.1.2.201"和"192.168.1.1"......
  • #yyds干货盘点 react笔记之学习之state组件
    前言我是歌谣我有个兄弟巅峰的时候排名c站总榜19叫前端小歌谣曾经我花了三年的时间创作了他现在我要用五年的时间超越他今天又是接近兄弟的一天人生难免坎坷大不了从......
  • #yyds干货盘点 react笔记之学习之state注意事项
    前言我是歌谣我有个兄弟巅峰的时候排名c站总榜19叫前端小歌谣曾经我花了三年的时间创作了他现在我要用五年的时间超越他今天又是接近兄弟的一天人生难免坎坷大不了从......
  • [leetcode每日一题]2.18
    ​​1237.找出给定方程的正整数解​​难度中等94给你一个函数  ​​f(x,y)​​ 和一个目标结果 ​​z​​,函数公式未知,请你计算方程 ​​f(x,y)==z​​ 所有可能......
  • #yyds干货盘点#Electron 开发音视频
    创建Electron项目前提条件在使用Electron进行开发之前,需要安装Node.js。要检查Node.js是否正确安装,请在您的终端输入以下命令:node-vnpm-v脚手架创建electron应用程......
  • #yyds干货盘点#【愚公系列】2023年02月 微信小程序-表格组件使用
    前言移动端的页面本应该很少有table表格这样的展示、操作,但总归有这样的需求,然而平时用的vant和iview的小程序组件库都没有table组件,这下面讲解表格组件封装的案例。githu......
  • [leetcode每日一题]2.17
    ​​1139.最大的以1为边界的正方形​​难度中等192给你一个由若干 ​​0​​ 和 ​​1​​ 组成的二维网格 ​​grid​​,请你找出边界全部由 ​​1​​ 组成的最......
  • #yyds干货盘点# LeetCode程序员面试金典:排序矩阵查找
    题目:给定M×N矩阵,每一行、每一列都按升序排列,请编写代码找出某元素。示例:现有矩阵matrix如下:[ [1, 4, 7,11,15], [2, 5, 8,12,19], [3, 6, 9,......