首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

给定一个排序数组和一个正整数k,求出1 <= i <= k的区间(100(i-1)/k,100(i)/k]内的整数个数

给定一个排序数组和一个正整数k,求出1 <= i <= k的区间(100(i-1)/k,100(i)/k]内的整数个数。

这个问题可以通过二分查找的方法来解决。首先,我们找到排序数组中第一个大于等于100(i-1)/k的元素的索引,记为left_index,然后找到第一个大于100(i)/k的元素的索引,记为right_index。那么,(100(i-1)/k,100(i)/k]内的整数个数就等于right_index - left_index。

下面是具体的算法步骤:

  1. 定义两个指针left和right,分别指向排序数组的第一个和最后一个元素。
  2. 使用二分查找来找到第一个大于等于100(i-1)/k的元素的索引,记为left_index。具体步骤如下:
    • 初始化left_index为-1。
    • while循环直到left大于right:
      • 计算中间元素的索引mid = (left + right) / 2。
      • 如果中间元素大于等于100(i-1)/k,则更新left_index为mid,并将right更新为mid-1。
      • 否则,更新left为mid+1。
  • 使用二分查找来找到第一个大于100(i)/k的元素的索引,记为right_index。具体步骤如下:
    • 初始化right_index为-1。
    • while循环直到left大于right:
      • 计算中间元素的索引mid = (left + right) / 2。
      • 如果中间元素大于100(i)/k,则更新right_index为mid,并将left更新为mid+1。
      • 否则,更新right为mid-1。
  • 返回right_index - left_index。

这个算法的时间复杂度为O(log n),其中n是排序数组的长度。以下是一个示例实现(使用JavaScript语言):

代码语言:txt
复制
function countNumbersInRange(nums, k) {
  const n = nums.length;
  let count = 0;
  
  for (let i = 1; i <= k; i++) {
    const targetLeft = 100 * (i - 1) / k;
    const targetRight = 100 * i / k;
    
    let left = 0;
    let right = n - 1;
    let leftIndex = -1;
    let rightIndex = -1;
    
    // Find the first element >= targetLeft
    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      
      if (nums[mid] >= targetLeft) {
        leftIndex = mid;
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    
    left = 0;
    right = n - 1;
    
    // Find the first element > targetRight
    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      
      if (nums[mid] > targetRight) {
        rightIndex = mid;
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    
    if (leftIndex !== -1 && rightIndex !== -1) {
      count += rightIndex - leftIndex;
    }
  }
  
  return count;
}

// Example usage:
const nums = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];
const k = 5;

const result = countNumbersInRange(nums, k);
console.log(result);  // Output: 4

请注意,这个问题与云计算、IT互联网领域的知识无直接关系,因此无需提及任何特定的云计算品牌商或产品。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

  • 2024-09-25:用go语言,给定一个长度为 n 整数数组 nums 一个正整数 k, 定义数组“能量“为所有k

    2024-09-25:用go语言,给定一个长度为 n 整数数组 nums 一个正整数 k, 定义数组"能量"为所有k 子序列数量之和。...请计算 nums 数组中所有子序列能量,并对结果取模 10^9 + 7 后返回。 输入:nums = [1,2,3], k = 3。 输出:6。...大体步骤如下: 1.定义一个数组 f 用于记录不同值下子序列数量,数组长度为 k+1,初始时令 f[0] = 1 表示为 0 时只有空子序列存在。...2.遍历给定整数数组 nums 中每个元素 x,对于每个 x,从 k 开始向前遍历到 0,更新 f[j] 值: • 如果当前值 j >= x,则更新 f[j] = (f[j]*2 + f[j-x]...总体时间复杂度是 O(n * k),其中 n 是 nums 长度,k给定正整数。 空间复杂度为 O(k)。

    15220

    2024-10-30:或值至少 K 最短子数组 I。用go语言,给定一个非负整数数组 nums 一个整数 k,我们需要判断数

    2024-10-30:或值至少 K 最短子数组 I。...用go语言,给定一个非负整数数组 nums 一个整数 k,我们需要判断数组中是否存在一个最短非空子数组,使得该子数组所有元素按位或(OR)运算结果至少为 k。...2.解决方案 1: • 对于每一个索引 i 从 0 到 n-1,表示当前子数组结束位置。 • 对于每一个 j 从 i 递减到 0,表示当前子数组起始位置。...• 检查从 j 到 i 这段子数组按位或结果,调用 isSpecial 函数。 • 如果返回结果满足大于等于 k,则更新 minLen 为当前子数组长度 i-j+1 最小值。...• 最后,如果没有找到满足条件数组,返回 -1;否则返回 minLen。 3.isSpecial 函数: • 接受数组 nums 数组起始、结束索引 j、i,以及目标值 k

    7410

    2023-05-16:给你一个 严格升序排列 正整数数组 arr 一个整数 k 。 请你找到这个数组里第 k 个缺失正整数。 输入:arr = [2,3,

    2023-05-16:给你一个 严格升序排列 正整数数组 arr 一个整数 k 。请你找到这个数组里第 k 个缺失正整数。输入:arr = 2,3,4,7,11, k = 5。输出:9。...答案2023-05-16:大体步骤如下:1.初始化左指针l为0,右指针r为数组长度减一,定义中间指针mfind(找到第k正整数下标位置),并将find初始化为数组长度。...3.如果当前位置arrm减去(m+1)大于等于k,说明第k个缺失正整数在当前位置左侧,更新find为当前位置m,并把右指针r设为m-1,继续二分查找左半部分。...4.如果当前位置arrm减去(m+1)小于k,说明第k个缺失正整数在当前位置右侧,把左指针l设为m+1,继续二分查找右半部分。...5.查找结束后,如果find等于0,说明要找是第一个缺失正整数,返回0即可;否则,找到第k正整数一个位置,把这个位置上元素赋值给preValue,计算从当前位置到第k正整数缺失数量under

    27610

    2023-09-13:用go语言,给定一个整数数组 nums 一个正整数 k, 找出是否有可能把这个数组分成 k 个非空子集,

    2023-09-13:用go语言,给定一个整数数组 nums 一个正整数 k, 找出是否有可能把这个数组分成 k 个非空子集,其总和都相等。...2.调用process1函数,传入数组nums、status初始值为0、sum初始值为0、sets初始值为0、limit为sum/kk一个dp map。...5.遍历数组nums,对于每个数字nums[i],判断该数字是否可以加入到当前子集中。...2.将数组nums按照从大到小顺序排序。 3.创建一个长度为k数组group,用于存放k个子集,初始值都为0。...4.调用partitionK函数,传入group、sum/k排序nums数组nums数组长度-1

    21940

    2024-06-26:用go语言,给定一个长度为n数组nums一个正整数k, 找到数组中所有相差绝对值恰好为k数组, 并

    2024-06-26:用go语言,给定一个长度为n数组nums一个正整数k, 找到数组中所有相差绝对值恰好为k数组, 并返回这些子数组中元素之和最大值。 如果找不到这样数组,返回0。...输入:nums = [-1,3,2,4,5], k = 3。 输出:11。 解释:好子数组中第一个元素最后一个元素绝对值必须为 3 。好子数组有 [-1,3,2] [2,4,5] 。...最大子数组为 11 ,对应数组为 [2,4,5] 。 答案2024-06-26: chatgpt 题目来自leetcode3026。...大体步骤如下: 1.初始化变量:设定初始答案 ans 为负无穷大(math.MinInt),创建一个 map minS 用来存储元素之和为某特定值最小下标,初始化总和 sum 为 0。...总额外空间复杂度也是 O(n),因为使用了一个 map 来存储元素之和为特定值最小下标,当输入数组中所有元素都不相差绝对值恰好为 k 时,map 中最多会存储 n 个元素。

    5520

    2022-04-13:给你一个下标从 0 开始包含 n 个正整数数组 arr ,一个正整数 k

    2022-04-13:给你一个下标从 0 开始包含 n 个正整数数组 arr ,一个正整数 k 。...如果对于每个满足 k <= i <= n-1 下标 i ,都有 arr[i-k] <= arr[i] ,那么我们称 arr 是 K 递增 。...每一次 操作 中,你可以选择一个下标 i 并将 arr[i] 改成任意 正整数。 请你返回对于给定 k ,使数组变成 K 递增 最少操作次数 。 力扣2111。...答案2022-04-13: 拆分成k个数组,分别求最长递增子序列,然后做差,最后求和。 代码用golang编写。..., start + 3k,....] // 辅助数组help,为了求最长递增子序列,需要开辟空间,具体看体系学习班 // 上面的序列,要改几个数,能都有序!

    41630

    2023-06-02:给定一个二进制数组 nums 一个整数 kk位翻转 就是从 nums 中选择一个长度为 k 数组, 同时把子数组一个 0

    2023-06-02:给定一个二进制数组 nums 一个整数 kk位翻转 就是从 nums 中选择一个长度为 k 数组,同时把子数组一个 0 都改成 1 ,把子数组一个 1 都改成...返回数组中不存在 0 所需最小 k位翻转 次数。如果不可能,则返回 -1。子数组数组 连续 部分。输入:nums = 0,1,0, K = 1。输出:2。...答案2023-06-02:大体步骤如下:1.初始化一个大小为 $n$ 队列 queue,用于存储需要翻转数组起始下标。...如果队列 queue 中元素个数为奇数,并且当前元素与队列最后一个元素不同,则将当前元素下标加入队列尾部,同时将翻转次数 ans 加 1。...需要注意是,在 C C++ 中,使用指针代替数组时需要手动分配释放内存,因此还需要额外空间来存储指向动态分配内存指针。

    50720

    2022-06-16:给定一个数组arr,含有n个数字,都是非负数, 给定一个正数k, 返回所有子序列中,累加最小k个子序列累加。 假设K不大,怎么算最

    2022-06-16:给定一个数组arr,含有n个数字,都是非负数, 给定一个正数k, 返回所有子序列中,累加最小k个子序列累加。 假设K不大,怎么算最快? 来自亚马逊。...答案2022-06-16: 排序,小根堆。 代码用rust编写。代码如下: fn main() { let mut nums: Vec = vec!..., ans); } fn top_min_sum2(arr: &mut Vec, k: i32) -> Vec { arr.sort(); // (最右下标,集合累加...[]; for _ in 0..k { ans.push(0); } // ans[0] = 0 // 0 1 2 k-1 // k个!...for i in 1..k { heap.sort_by(|a, b| b[1].cmp(&a[1])); let cur = heap.pop().unwrap();

    49640

    2022-10-30:给你一个长度为 n 整数数组 rolls 一个整数 k 。 你扔一个 k 面的骰子 n 次,骰子每个面分别是 1k , 其中第

    2022-10-30:给你一个长度为 n 整数数组 rolls 一个整数 k 。...你扔一个 k 面的骰子 n 次,骰子每个面分别是 1k , 其中第 i 次扔得到数字是 rollsi 。 请你返回 无法 从 rolls 中得到 最短 骰子子序列长度。...扔一个 k 面的骰子 len 次得到一个长度为 len 骰子子序列 。 注意 ,子序列只需要保持在原数组顺序,不需要连续。...>, k: i32) -> i32 { // 1~k上,某个数字是否收集到了!...mut set: Vec = repeat(false).take((k + 1) as usize).collect(); // 当前这一套,收集了几个数字了?

    31510

    1. 基础算法初识

    如果数组中不存在该元素,则返回 -1 -1。 输入格式 第一行包含整数 n q,表示数组长度询问个数。 第二行包含 n 个整数(均在 1∼10000 范围),表示完整数组。...高精度加法 原题链接 描述 给定两个正整数(不含前导 0),计算它们。 输入格式 共两行,每行包含一个整数。 输出格式 共一行,包含所求。...a[i]=b[i]-b[i-1]; } 应用及原理 对于一个数组给定边界lr,可以构造其一维前缀和数组快速求出区间内元素 //给定一个数组a[N],构造其前缀和数组为b[N],查询l到r区间元素...1个数 原题链接 描述 给定一个长度为 n 数列,请你求出数列中每个数二进制表示中 1 个数。...输入格式 多实例测试,每次输入为一个正整数N(1≤N≤1000000) 输出格式 运行结果每个数1行,结果中个数是输入正整数在素数集合中排位。

    36630

    1. 基础算法初识

    高精度加法 原题链接 描述 给定两个正整数(不含前导 0),计算它们。 输入格式 共两行,每行包含一个整数。 输出格式 共一行,包含所求。...a[i]=b[i]-b[i-1]; } 应用及原理 对于一个数组给定边界lr,可以构造其一维前缀和数组快速求出区间内元素 //给定一个数组a[N],构造其前缀和数组为b[N],查询l到r区间元素...i-1][j-1]; } } 应用及原理 对于一个二维数组给定(x1,y1)(x2,y2),求以(x1,y1)为左上角到以(x2,y2)为右下角子矩阵中所有元素 /* 给定一个二维数组...1个数 原题链接 描述 给定一个长度为 n 数列,请你求出数列中每个数二进制表示中 1 个数。...输入格式 多实例测试,每次输入为一个正整数N(1≤N≤1000000) 输出格式 运行结果每个数1行,结果中个数是输入正整数在素数集合中排位。

    30320

    2024-09-11:用go语言,给定一个从0开始整数数组nums一个正奇数整数k, 要求在nums数组中选择k个不重叠

    2024-09-11:用go语言,给定一个从0开始整数数组nums一个正奇数整数k, 要求在nums数组中选择k个不重叠数组, 使得这些子数组能量值之和最大。...输入:nums = [1,2,3,-1,2], k = 3。 输出:22。 解释:选择 3 个子数组最好方式是选择:nums[0..2] ,nums[3..3] nums[4..4] 。...大体步骤如下: 1.创建长度为 n+1 累积和数组 s,其中 s[i] 存储前 i 个元素。 2.创建长度为 n+1 数组 f,用于存放最大能量值累积。...3.循环k次,表示每次选择一个数组过程: 3.a.初始化 pre 为 f[i-1],f[i-1] 为负无穷大,设置初始最大值为负无穷大,定义一个权重 w。...3.b.从第 i 个位置开始循环到 n-k+i 位置,计算每次选择一个数组最大能量值,并更新 f[j]。 4.返回最终最大能量值 f[n]。

    8520

    2021-08-09:给定一个有正、有负、有0数组arr,给定一个整数k,返回arr子集是否能累加出k1)正常怎么做?2)

    2021-08-09:给定一个有正、有负、有0数组arr,给定一个整数k,返回arr子集是否能累加出k1)正常怎么做?2)如果arr中数值很大,但是arr长度不大,怎么做?...福大大 答案2021-08-09: 将数组划分成两部分,对左部分右部分用动态规划。 代码用golang编写。...arr数字个数不算多(40以内),哪怕其中数值很大,分治方法也将是最优解 func isSum4(arr []int, sum int) bool { if sum == 0 {...,包含左部分一个数也没有,这种情况,leftsum表里,0 // 17 17 for l, _ := range leftSum { if _, ok := rightSum...形成累加是pre // arr[i...end - 1] end(终止) 所有数字随意选择, // arr[0...end-1]所有可能累加存到ans里去 func process4(arr

    34030

    2024-06-01:用go语言,给定一个从0开始索引整数数组 nums 、两个正整数 k dist 。 数组代价是该数

    2024-06-01:用go语言,给定一个从0开始索引整数数组 nums 、两个正整数 k dist 。 数组代价是该数组一个元素。...问题要求将数组 nums 分割成 k 个连续且不重叠数组, 同时确保第二个到第k个子数组一个元素与它前面的子数组最后一个元素距离不超过 dist 。...换句话说,要把数组分割成这样数组: nums[0..(i1 - 1)], nums[i1..(i2 - 1)], ..., nums[ik-1.....(n - 1)], 并且满足 ik-1 - i1 <= dist 。 问题目标是求得这些子数组代价之和最小值。...• 维护堆大小,保持堆 l 大小在 k-1 k+1 之间。 • 计算当前代价 mn,并更新为当前最小值。 5.最后返回数组一个元素与最小代价 mn 作为最终结果。

    9720

    2022-11-03:给定一个数组arr,一个正数k 如果arr == 0,表示i这里既可以是左括号也可以是右括号, 而且可以涂上1~k每一种颜色 如果

    2022-11-03:给定一个数组arr,一个正数k如果arri == 0,表示i这里既可以是左括号也可以是右括号,而且可以涂上1~k每一种颜色如果arri !...a * k.pow(((n - (b > 1) as u32) };}// 忽略染色这件事,求合法括号结合数量fn combines(arr: &mut Vec) ->...p1 + p2; }}// 在arr[i...]范围上做决定// 之前在arr[0...i-1]上决定,使得左括号比右括号多了j个// 最终合法括号结合是多少fn f(arr: &mut Vec...+ 1, j - 1, dp); } dp[i as usize][j as usize] = ans; return ans;}// 生成长度随机数组// 值在0~K之间,但是50%...概率值是0,50%概率值是1~k一个fn random_array(n: i32, k: i32) -> Vec { let mut ans = vec!

    28520
    领券