首页 > 试题广场 >

数字在升序数组中出现的次数

[编程题]数字在升序数组中出现的次数

热度指数：615117 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数

数据范围： $0 \le n \le 1000 , 0 \le k \le 100$ ，数组中每个元素的值满足 $0 \le val \le 100$
要求：空间复杂度 $O(1)$ ，时间复杂度 $O(logn)$

示例1

输入

[1,2,3,3,3,3,4,5],3

输出

示例2

输入

[1,3,4,5],6

输出

算法知识视频讲解

Java

*.初见

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @param k int整型
     * @return int整型
     */
    public int GetNumberOfK (int[] nums, int k) {
        // write code here
       if(nums==null||nums.length==0)
    		return 0;
    	if(nums.length==1){
    		if(nums[0]==k)
    			return 1;
    		return 0;
    	}
    	String ss = Arrays.toString(nums).trim();
    //	System.out.println(ss);
    	ss=ss.replaceAll(" ", "");
    	ss=ss.replace('[', ',');
    //	System.out.println(ss);
    	return (ss.length()-ss.replaceAll(","+k,"").length())*((""+k).length())/(((""+k).length()+1)*(""+k).length());
    }
}

发表于 2025-01-30 16:36:49 回复(0)

Java

୧⍢⃝୨

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @param k int整型
     * @return int整型
     */
    public int GetNumberOfK (int[] nums, int k) {
        int n = nums.length;
        int l = 0;
        int r = n - 1;
        int res = 0;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == k) {
                int ll = mid - 1, rr = mid + 1;
                res++;
                while (ll >= 0) {
                    if (nums[ll--] == k) {
                        res++;
                    } else {
                        break;
                    }
                }
                while (rr < n) {
                    if (nums[rr++] == k) {
                        res++;
                    } else {
                        break;
                    }
                }
                break;
            }
            if (nums[mid] < k) {
                l = mid + 1;
            }
            if (nums[mid] > k) {
                r = mid - 1;
            }
        }
        return res;
    }
}

发表于 2024-08-03 15:45:26 回复(0)

Java

牛客839384289号

public int GetNumberOfK (int[] nums, int k) {
    // write code here
    int res=0;
    for(int n : nums){
        if(n==k){
            res++;
        }
    }
    return res;
}

编辑于 2024-03-24 12:56:41 回复(0)

Java

占领智商盆地

 public int GetNumberOfK (int[] nums, int k) {
        // write code here
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {

            if (hashMap.containsKey(nums[i])) {
                int value = hashMap.get(nums[i]);
                hashMap.put(nums[i], ++value );
            } else {
                hashMap.put(nums[i], 1);
            }

        }
        for (int j = 0; j < nums.length; j++) {
            if (hashMap.containsKey(k)) {
                return hashMap.get(k);
            }
        }
        return 0;
    }

编辑于 2024-02-26 20:04:30 回复(0)

Java

已注销

public class Solution {
    public int GetNumberOfK(int [] array, int k) {
        int num = 0;
        if (array.length == 0) {
            return num;
        }
        for (int i = 0; i < array.length; i++) {
            if (array[i] == k) {
                num++;
            }
        }
        return num;
    }
}
这样可以嘛😂

发表于 2023-04-18 09:22:17 回复(1)

Java

Hadoopdoop

import java.util.Arrays;
public class Solution {
    public int GetNumberOfK(int [] a , int key) {
        return (int)Arrays.stream(a).filter(e -> e == key).count();
    }
}

发表于 2023-03-09 20:25:46 回复(0)

Java

ludvig

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        int low = 0;
        int high = array.length-1;
        int i = 0;
        int j = array.length-1;
        boolean flag = false;
        //两次二分查找
        while(low<=high){
            int medium = (low+high)/2;
            if(array[medium]==k){
                flag = true;
                if(medium>=1 && array[medium-1]<k){
                    i = medium;
                    break;
                }else{
                    high=medium-1;
                }
            }
            if(array[medium]<k){
                low = medium+1;
            }
            if(array[medium]>k){
                high = medium-1;
            }
        }

        low = 0;
        high = array.length-1;

        while(low<=high){
            int medium = (low+high)/2;
            if(array[medium]==k){
                if(medium+1<array.length && array[medium+1]>k){
                    j = medium;
                    break;
                }else{
                    low=medium+1;
                }
            }
            if(array[medium]<k){
                low = medium+1;
            }
            if(array[medium]>k){
                high = medium-1;
            }
        }
        if(flag){
            return j-i+1;
        }else{
            return 0;
        }
    }
}

发表于 2022-11-03 10:31:38 回复(0)

Java

zhaoxfan

import java.util.*;
public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        int l=0, r=array.length-1;
        while(l<r) {
            int mid = (l+r)/2;
            if(array[mid] < k) l = mid+1;
            else if(array[mid] > k) r = mid-1;
            else break;
        }
        int count=0;
        for(int i=l; i<=r; i++) {
            if(array[i] == k) count++;
        }
        return count;
    }
}

发表于 2022-08-03 12:44:55 回复(0)

Java

牛客888828564号

import java.util.*;
public class Solution {
    //二分查找
    public int bin(int[] arr, double n) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (arr[mid] < n)
                left = mid + 1;
            else if (arr[mid] > n)
                right = mid - 1;
        }
        return left;
    }

    public int GetNumberOfK(int [] array, int k) {
        if (array.length == 0)
            return 0;
        int res_right = bin(array, k + 0.5);//右指针
        int res_left =  bin(array, k - 0.5);//左指针
        //以下判断保证左右指针落在闭区间内
        //如array为[2,3,3,3,4]的话,left和right在下标1和3处
        //首先判断数组里只有一种数的情况
        //因为二分搜索结果必然是刚好等于K,或者在k的前一位或后一位
        //[3,3,3]左右指针在下标0和2处，
        //[1,2,3,3]左指针在下标1处，右指针在下标3处
        //[3,3,4,5]左指针在下标0处，右指针在下标2处
        //可以观察到只有一种数时左右指针必然是在闭区间内的
        //只要大于一种数,左右指针就会落在区间外一位
        
        if (array[res_left] == array[res_right]&&array[res_left]==k)
            return res_right - res_left + 1;
        if (res_left == res_right)//只有一种数但不等于搜索的数时左右指针会重合
            return 0;
        //判断完只有一种数的情况剩余的情况必然大于一种数，即左指针或右指针在区间外一位
        if (array[res_right] != k)
            res_right = res_right - 1;
        if (array[res_left] != k)
            res_left = res_left + 1;

        return res_right  - res_left + 1;
    }

}

发表于 2022-07-13 10:19:59 回复(0)

Java

NorthXwind

import java.util.*;

public class Solution {
    public int GetNumberOfK(int [] array, int k) {
        HashMap<Integer, Integer> res = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            if (res.containsKey(array[i])) {
                res.put(array[i], res.get(array[i]) + 1);
            } else {
                res.put(array[i], 1);
            }
        }

        return res.containsKey(k) ? res.get(k) : 0;
    }
}

发表于 2022-06-16 16:48:19 回复(0)

Java

刘笔

先用二分查找，在找到目标之后，使左右指针向中间收缩，直到与目标值相等为止，此时左右指针即分别指向第一个目标值和最后一个目标值的位置，目标值出现次数即为右指针-左指针+1

public class Solution {
    public int GetNumberOfK(int [] array, int k) {
        int left = 0, right = array.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (array[mid] > k) {
                right = mid - 1;
            }
            if (array[mid] < k) {
                left = mid + 1;
            } 
            if (array[mid] == k) {
                //mid找到了目标值，左右指针向中间缩，直到遇到目标值
                while(array[right] != k)
                    right--;
                while(array[left] != k)
                    left++;
                break;
            }
        }
        return right - left + 1;
    }
}

发表于 2022-04-29 13:05:19 回复(0)

Java

忘萤之殇

public class Solution {
    public int GetNumberOfK(int [] array, int k) {
        if(array.length==0){
            return 0;
        }
        int count = 0;  //统计个数
        int left = 0;  //左边的下标
        int right = array.length - 1; //右边的下标
        while (left<array.length) {//从零开始遍历，直到找到等于k的下标
            if(array[left]==k){
                break;
            }else{
                left++;
            }
        }
        while(right>=0){//从最大值开始遍历，直到找到等于k的下标
            if(array[right]==k){
                break;
            }else{
                right--;
            }
        }
        if(left>=array.length||right<0){//如果没有找到就输出0，否则就输出左右下标的差值加1
            return 0;
        }else{
            return right-left+1;
        }
    }
}

发表于 2022-04-18 19:19:13 回复(0)

Java

624huiguorou

升序而且复杂度要求O(logn)，用二分查找。

但是一次二分不行，所以找k+0.5和k-0.5的插入位置。

当mid对应元素大于k+0.5时，说明k+0.5应该插入在mid前面(即end=mid-1)

当mid对应元素小于k+0.5时，k+0.5应该插入在mid后面(即start=mid+1)

最后start为应该插入的位置

k-0.5同理。

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        //找到k+0.5和k-0.5分别应该插入的下标
        return binarySearch(array, k+0.5) - binarySearch(array, k-0.5);
    }
    
    //找到浮点数a应该插入的下标
    //（拿3来说。2.5应该插入到第一个3的位置，3.5应该插入到最后一个3后面的位置）
    public int binarySearch(int[] array, double a){
        int start = 0, end = array.length-1;
        while(start <= end){
            //防止溢出的写法
            int mid = start + (end - start) / 2;
            //如果mid对应元素大于a则应插入在mid前面
            if(array[mid] > a){
                end = mid - 1;
            }else{
                //如果小于a则应插入在mid后面
                start = mid + 1;
            }
        }
        //最后start为对应结果
        return start;
    }
}

发表于 2022-03-26 17:24:10 回复(0)

Java

牛客841422626号

看了半天才搞懂区间条件的我太菜了

发表于 2022-03-12 01:25:16 回复(0)

Java

P1nkFloyd

用ArrayList的indexOf方法

import java.util.ArrayList;

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if(!contain(array, k))
            return 0;
        ArrayList<Integer> a1 = new ArrayList<>();
        ArrayList<Integer> a2 = new ArrayList<>();
        for(int i = 0; i < array.length; i++){
            a1.add(array[i]);
            a2.add(array[array.length - i - 1]);
        }
        return array.length - a1.indexOf(k) - a2.indexOf(k);
    }
    
    private boolean contain(int[] array , int k){
        if(array.length == 0)
            return false;
        for(int i = 0; i < array.length; i++){
            if(array[i]==k)
                return true;
        }
        return false;
    }
}

发表于 2022-03-08 18:22:54 回复(0)

Java

thai

虽然，但是。。。

import java.util.Arrays;
public class Solution {
    public int GetNumberOfK(int [] a , int key) {
        return (int)Arrays.stream(a).filter(e -> e == key).count();
    }
}

发表于 2022-03-05 00:17:04 回复(0)

Java

牛客989812257号

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        int left = -1, right = array.length;
        int leftBorder = 0,rightBorder = 0;
        // 寻找左边界 找到第一个<k的数
        while(left+1 != right){
            int mid = (left+right)>>1;
            if(array[mid] < k){
                left = mid;
            } else {
                right = mid;
            }
        }
        leftBorder = left;
        // 寻找右边界 找到第一个>k的数
        left = -1; right = array.length;
        while(left+1 != right){
            int mid = (left+right)>>1;
            if(array[mid] <= k){
                left = mid;
            } else {
                right = mid;
            }
        }
        rightBorder = right;
        return rightBorder-leftBorder-1;
    }
}

发表于 2022-01-29 23:02:13 回复(0)