统计一维数组中元素出现次数

针对MS面试中出现的问题,提出了一种改进版的二分查找算法。该算法首先对数组进行排序,然后利用变形的二分查找定位重复元素的范围,有效提升了查找效率并降低了空间复杂度。

之前ms面试题的算法设计被问了这个。

也许这就是“挂面”的原因。反省自己的浮躁,还有更优的解法。

最近看chord收到二分查找的启发,其实可以这样设计算法的:

首先对数组排序,时间复杂度O(NlogN)。

之后变成了abbc……这样有序形式,接着用变形的二分查找,定位同一个元素出现的范围。

比如说第一个b的下标是1,那么二分范围是1~(len-1),每一次根据end是否是b来划分区间(若是b则区间:mid~end,若不是b则区间:start~mid)算法结束条件是end-start==1。

然后下一个元素开始的起点是之前元素的find+1位置,这样在大量元素的情况下,算法的效率是O(Nlog(N)+Klog(N)),其中K是元素的种类,是个常数。

比起直接遍历数组的统计方法,这种方法可以省掉不必要的空间开销。空间复杂度仅为O(1)。

看来之前对二分查找的理解还不够深刻,深刻反省自己。。。

在二维数组中统计特定元素的出现次数,可以通过遍历数组中的每个元素来实现。以下是一些不同编程语言中的实现方法: ### Java 实现 在 Java 中,可以使用嵌套循环来遍历二维数组,并通过一个计数器变量来统计特定值的出现次数: ```java int target = 5; // 目标值 int count = 0; // 计数器,用于统计目标值出现的次数 for (int row = 0; row < arr.length; row++) { // 遍历二维数组的行 for (int col = 0; col < arr[row].length; col++) { // 遍历二维数组的列 if (arr[row][col] == target) { // 如果当前元素等于目标值 count++; // 增加计数 } } } System.out.println("元素 " + target + " 出现的次数:" + count); // 输出目标值出现的次数 [^1] ``` ### Python 实现 在 Python 中,可以利用 `collections.Counter` 来简化统计过程,或者直接使用双重循环来遍历二维数组: ```python from collections import Counter # 假设有一个二维数组 matrix = [[0, 0, 1], [1, 1, 3], [4, 5, 6]] # 将二维数组展平为一维列表 flat_list = [item for sublist in matrix for item in sublist] # 使用Counter统计特定值的出现次数 target = 1 count = flat_list.count(target) print(f"元素 {target} 出现的次数:{count}") ``` ### JavaScript 实现 在 JavaScript 中,可以创建一个对象来存储每个元素的出现次数: ```javascript function countOccurrences(matrix) { let counts = {}; // 创建一个空对象用于存储结果 matrix.forEach(row => { row.forEach(item => { if (counts[item]) { counts[item]++; // 如果该元素已经在对象中,增加计数 } else { counts[item] = 1; // 如果该元素不在对象中,添加到对象并设置计数为1 } }); }); return counts; // 返回结果对象 } // 示例用法 let matrix = [[0, 0, 1], [1, 1, 3], [4, 5, 6]]; console.log(countOccurrences(matrix)); ``` ### C 语言实现 在 C 语言中,可以通过嵌套循环来遍历二维数组,并通过条件判断来统计特定值的出现次数: ```c #include <stdio.h> #define ROWS 3 #define COLS 3 int main() { int matrix[ROWS][COLS] = {{0, 0, 1}, {1, 1, 3}, {4, 5, 6}}; int target = 1; int count = 0; for (int row = 0; row < ROWS; row++) { for (int col = 0; col < COLS; col++) { if (matrix[row][col] == target) { count++; } } } printf("元素 %d 出现的次数:%d\n", target, count); return 0; } ``` 以上代码示例展示了如何在不同的编程语言中统计二维数组中特定元素的出现次数
评论 2
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值