n个[0,n)的数，求每个数的出现次数（不能开辟额外空间）

一时失言乱红尘 2023-06-30 08:37 2阅读 0赞

## 问题： ##

问题：n个\[0,n)的数，求每个数的出现次数（不能开辟额外空间）

如：  
![在这里插入图片描述][20200115184732775.png]  
在不占用额外空间的情况下，求出每个数字出现的次数。

## 解答： ##

分析得：

*  n 个不超过 n 的数字，可以利用取模和除数来思考
 *  可以遍历所有数据，然后在每个数据作为下标的位置处加上一个 n ，此时：
 *  每个位置的数据**取余 n 就是其原始数据**；
 *  每个位置的数据**除以 n 就是其出现次数**。

如：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTY4MDgw_size_16_color_FFFFFF_t_70]  
**代码：**

#include <stdio.h>
    
    int main(int argc, char const *argv[])
    { 
    	int array[] = { 1, 2, 1, 4, 1};
    	int n = sizeof(array) / sizeof(array[0]);
    	int i = 0;
    	for(i = 0; i < n; i++){ 
    		array[array[i] % n] += n;
    	}
    	for(i = 0; i < n; i++){ 
    		printf("%d：%d次\n", i, array[i] / n);
    	}
    	return 0;
    }

[20200115184732775.png]: https://img-blog.csdnimg.cn/20200115184732775.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTY4MDgw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200115185252396.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTY4MDgw,size_16,color_FFFFFF,t_70

发表评论取消回复

表情：

评论列表（有 0 条评论，2人围观）

还没有评论，来说两句吧...

相关阅读

相关找到第n个数，

find the nth digit Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K

「爱情、让人受尽委屈。」/ 2024年02月18日 23:15/ 0 赞/ 26 阅读

相关 n个数求前m个数的大小

一、描述 n个数求前m个数的大小二、分析堆排序就是先求出最大的数，然后求出次大的数，然后求出第三大的数，依次类推，而这个题只要求求出前m个大的数，所以用堆排序应该是效

布满荆棘的人生/ 2023年12月31日 07:20/ 0 赞/ 17 阅读

相关 n个[0,n)的数，求每个数的出现次数（不能开辟额外空间）

问题：问题：n个\[0,n)的数，求每个数的出现次数（不能开辟额外空间）如： ![在这里插入图片描述][20200115184732775.png] 在不占

一时失言乱红尘/ 2023年06月30日 08:37/ 0 赞/ 3 阅读

相关 java n个数的和_Java如何求n个数字的和？

在Java编程中，如何求n个数字的和？以下示例演示了如何使用堆栈的概念来将n个自然数相加求和。 package com.yiibai; import java.io.IO

淡淡的烟草味﹌/ 2022年11月02日 13:16/ 0 赞/ 198 阅读

相关 162-求第N个丑数的值

什么是丑数？把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数，但7、14不是，因为它们包含质因子7。习惯上我们把1当做是第一个丑数。

我会带着你远行/ 2022年10月24日 13:27/ 0 赞/ 165 阅读

相关给定n个数，求n个数的两两异或和

给定n个数，求n个数的两两异或和 include <bits/stdc++> using namespace std; define ll long

悠悠/ 2022年08月30日 04:10/ 0 赞/ 253 阅读

相关 N^N的最右边的数

N^N的最右边的数方法一：找规律 include <iostream> include <cmath> using namespace std;

灰太狼/ 2022年06月16日 13:08/ 0 赞/ 119 阅读

相关求阶梯状数组的层数和第n行的第一个数和第n个数？

<?php header('content-type:text/html;charset=utf-8;'); $max_num

亦凉/ 2022年05月31日 12:09/ 0 赞/ 223 阅读

相关 JavaScript求n个数的最大值

<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Document</

╰+攻爆jí腚メ/ 2022年05月20日 02:57/ 0 赞/ 230 阅读

相关 N数之和

目录两数之和三数之和四数之和 -------------------- 两数之和 [https://leetcode-cn.com/problems

矫情吗；*/ 2022年05月10日 01:56/ 0 赞/ 159 阅读