一道算法题:查找数组 arr 中第 k 小的奇数

题目描述

查找数组 arr 中第 k 小的奇数,如果不存在则返回 0. (arr [i] > 0 (i>=0))

计算出时间复杂度(注意代码注释,尽可能不用全排序,不要使⽤库函数或脚本中已经实现好的排序算法和⼯具,需要⾃⼰实现数据结构和所需要的算法)

解题方案

思路

  • 属于 Top K 问题
  • 假设数组中数据范围有限,使用「计数排序法」
  • 时间复杂度:O(N),N 为第 k 小的奇数的大小
  • 最坏时间复杂度:当不存在时,需要遍历完 counter 数组,O(M),M 为指定数组的范围
  • 空间复杂度:O(M),需要长度为 M 的额外数组。

代码

// Java
class Solution {
public int findKth(int[] arr, int k) {
if (k == 0) {
return 0;
}
// 统计每个数字出现的次数
int[] counter = new int[10001];
for (int num : arr) {
counter[num] = counter[num] + 1;
}
int x = 0;
// 遍历 counter,查找第 k 小的奇数
for (int num = 0; num < counter.length; num++) {
if (counter[num] > 0 && x < k && num % 2 == 1) {
x++;
}
if (x == k) {
return num;
}
}
return 0;
}
}

测试代码

public static void main(String[] args) {
int[] arr = {1, 4, 23, 2, 6, 9, 13, 5, 45, 12};
int k = 3;
System.out.println(new Solution().findKth(arr, k));
}
DeppWang wechat
个人公众号