首页 > 其他分享 >【数组8】数字在排序数组中出现的次数

【数组8】数字在排序数组中出现的次数

时间:2022-11-22 12:01:32浏览次数:41  
标签:return nums int 次数 midIndex 数组 end 排序 start


题目描述

统计一个数字在排序数组中出现的次数。

public class Solution {
public int GetNumberOfK(int [] array , int k) {
if(array==null||array.length<=0)
return 0;
int first=-1;
int last=-1;
//找到第一次出现的位置
for(int i=0;i<array.length;i++){
if(array[i]==k){
first=i;
break;
}
}
//第一遍查询没有k值直接返回0
if(first==-1)
return 0;
//找到最后一次出现的位置
for(int j=array.length-1;j>=0;j--){
if(array[j]==k){
last=j;
break;
}
}
return (last-first+1);
}
}




解法一:时间复杂度O(n)

public class Solution {
public int GetNumberOfK(int [] nums , int k) {
if(nums==null ||nums.length<=0)
return 0;
int len=nums.length;
//只有一个数
if(len==1){
if(nums[0]==k)
return 1;
}
int firstK=0;
int lastK=0;
int i=0;
while(i<len){
if(nums[i]==k){
firstK=i;
break;
}
i++;
}
int j=len-1;
while(j>0){
if(nums[j]==k){
lastK=j;
break;
}
j--;
}
//不存在K
if(lastK==0 &&firstK==0){
return 0;
}
int times=lastK-firstK;
if(times>=0)
return times+1;
return 0;
}
}


解法二:二分查找法,时间复杂度O(logn)

public class Solution {
public int GetNumberOfK(int [] nums , int k) {
if(nums==null||nums.length<=0)
return 0;
int len=nums.length;
int firstK=GetFirstK(nums,0,len-1,k);
int lastK=GetLastK(nums,0,len-1,k);
int times=0;
if(firstK>=0 &&lastK>=0)
times= lastK-firstK+1;
return times;
}
private int GetFirstK(int[]nums,int start,int end,int k){
if(start>end)
return -1;
int midIndex=(end+start)/2;
int midVal=nums[midIndex];
if(midVal==k){
if(((midIndex>0 &&nums[midIndex-1]!=k))||midIndex==0){
return midIndex;
}else{
end=midIndex-1;
}
}else if(midVal>k){
end=midIndex-1;
}else{
start=midIndex+1;
}
return GetFirstK(nums,start,end,k);
}
private int GetLastK(int[]nums,int start,int end,int k){
if(start>end)
return -1;
int midIndex=(end+start)/2;
int midVal=nums[midIndex];
if(midVal==k){
if(((midIndex<nums.length-1 &&nums[midIndex+1]!=k))||midIndex==nums.length-1){
return midIndex;
}else{
start=midIndex+1;
}
}else if(midVal>k){
end=midIndex-1;
}else{
start=midIndex+1;
}
return GetLastK(nums,start,end,k);
}
}



标签:return,nums,int,次数,midIndex,数组,end,排序,start
From: https://blog.51cto.com/u_15886477/5877575

相关文章

  • 【数组9】数组中只出现一次的数字
    题目描述一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。更好的方法://num1,num2分别为长度为1的数组。传出参数//将num1[0]......
  • 【数组7】把数组排成最小的数
    题目描述输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323......
  • 【字符串3】-整数中1出现的次数(从1到n整数中1出现的次数)
    求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数?为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。......
  • 排序算法(实践篇)
    排序算法(实践篇)插入排序直接插入voidinsert_sort(intq[],intn){ inti,j; for(i=2;i<=n;i++) { if(q[i]<q[i-1])//q[i]<q[i-1]说明要将q[i]插入前面的有......
  • 排序算法(理论篇)
    排序算法(理论篇)插入排序直接插入:时间:O(n2);空间:O(1)比较次数分析最好情况(全正序):n-1次最坏情况(全逆序):n(n-1)/2次一般情况分析举例:对于21,32,46,40的序列从小......
  • php中的array_unshift() 新增一个元素在数组开头 -- 简单实现
    array_unshiftarray_unshift()函数在数组开头插入一个或多个元素。被加上的元素作为一个整体添加,这些元素在数组中的顺序和在参数中的顺序一样。该函数会返回数组中元素......
  • 二叉排序树(BST树)
    二叉排序树(BST树)一、介绍二叉排序树:所有叶子结点都要求左子结点比当前结点小,右子结点比当前结点大。优点:查询速度,新增结点速度都会更快。每判断一个结点,都会选择去往......
  • NumPy笔记(2)—— 使用数组进行面向数组编程
    参考:《利用python进行数据分析》第4章注意,由于本文是jupyter文档转换来的,代码不一定可以直接运行,有些注释是jupyter给出的交互结果,而非运行结果!!文章目录​​1.生成网格数......
  • 数组,对象解构
    数组解构varnames=["abc","cba",undefined,"nba","mba"]基本使用var[name1,name2,name3]=names顺序问题:严格的顺序var[name1,,nam......
  • C#中byte[]字节数组复制的常用方法
    简单总结了5种字节数组的复制方法for循环实现复制较为原始的遍历写法,不太推荐byte[]data=newbyte[]{0,1,2,3,4,5,6,7,8,9};byte[]data1=newbyte[data.length]......