一、问题描述
【题型一】
一个长度大小为n的数组，数组中的每个元素的取值范围在[1,n]，且为正整数。
问：如何在时间复杂度为O(n)，空间复杂度为O(1)的条件下，统计数组中不同元素出现的次数。
【题型二】
在一个长度为n的数组里的所有数字都在0-n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
【例如】
如果输入长度为7的数组(2,3,1,0,2,5,3)，那么对应的输出是重复的数字2或者3
二、解题思路
【题型一】
数组按序扫描，通过当前元素的值作为下标，找到下一个元素。最后得到的数组中，下标（因为下标从0开始的，故输出时需要+1）为数组中出现的元素，每个下标对应的值取反输出即是该元素出现的频率。
若当前元素小于0，
则跳过；
若当前元素大于0，
则判断其作为下标索引到的元素是否大于0，
若大于0，则索引到的元素赋值给当前元素，索引到的元素置为-1；
若小于0，则索引到的元素自减1，当前元素置为0；
用正数/负数来区分a[i]上是原来的值，还是用于计数的值
随便举个例子，比如 { 2, 5, 5, 2, 3 }
看到第一个是 2，即2有1个，所以先将这个“1”保存到a[2-1]的位置上。但a[2-1]有有效数呀，咋办？移动一下就行。假设我不用负数，而是用中括号来表示计数，步骤依次是
{ 2, 5, 5, 2, 3 }
5, [1], 5, 2, 3
3, [1], 5, 2, [1]
5, [1], [1], 2, [1]
[0], [1], [1], 2, [2]
[0], [2], [1], [0], [2]
结果是 1有0个, 2有2个， 3有1个， 4有0个， 5有2个
此类以值做下标的方法适用条件：
正整数
取值范围[1,n]
n个数
【题型二】
思路一：排序 -- 时间复杂度O(nlogn)
思路二：哈希表 -- 时间复杂度O(1) 空间复杂度O(n)
思路三：值为下标 -- 时间复杂度O(n) 空间复杂度O(1)
思路三：以2,3,1,0,2,5,3为例
1）数组第0号位置为2，2!=0，将0号位置的2与2号位置的1交换，变成 1,3,2,0,2,5,3
2）数组第0号位置为1，1!=0，将0号位置的1与1号位置的3交换，变成 3,1,2,0,2,5,3
3）数组第0号位置为3，3!=0，将0号位置的3与3号位置的0交换，变成 0,1,2,3,2,5,3
4）数组第0号位置为0，0==0，游标右移至第1号位置，1==1，继续右移，直到第4号位置
5）数组第4号位置为2, 2!=4, 2==array[2]，说明2重复了，输出2，算法结束
思路三前提条件：
1）数组中数字范围为[0,n-1]
2）数组长度为n
三、算法代码
【题型一】n个正整数 -- [1,n] 找重复
#include <stdio.h>
#include <stdlib.h>
/*******************************
Author:tmw
date:2018-3-17
********************************/
int* mark_times_appear(int* array, int len)
{
if(array==NULL || len<0) return NULL;
int index = 0;
int i = 0;
while(i<len)
{
/**当前位为正数有效位，则执行交换**/
while( array[i] > 0 )
{
index = array[i];
/**待交换的位置上的元素是有效值的情况：
交换，并将当前待交换的元素下的值改成负数计数值
**/
if(array[index-1]>0) /**数组下标从0开始**/
{
array[i] = array[index-1];
array[index-1] = -1;
}
/**待交换的位置上的元素是负数的情况：
说明该元素出现过一次了，负数计数需要减减来更新记录
**/
else/**若需要返回出现两次的元素，可以直接在这里做返回**/
{
//return array[i];
array[i] = 0;
array[index-1]--;
}
}
/**当前位为负数，紧接着判断下一位**/
i++;
}
return array;
}
【题型二】n个数[0,n] 找重复
/**************************************************
author:tmw
date:2018-8-22
**************************************************/
#include <stdio.h>
#include <stdlib.h>
#define swap(a,b,t) (t=a,a=b,b=t)
/** findDuplicatedNumber 找到任意一个重复的元素并输出
* @param int* array -- 存数字的数组
* @param int array_len -- 数组长度
**/
int findDuplicatedNumber( int* array, int array_len )
{
/**入参判断**/
if( array == NULL || array_len <= 0 )
return -1;
int i;
/**这一步可省略：验证数组内的元素满足给定条件：元素取值[0,n-1]，长度为n**/
for( i=0; i<array_len; i++ )
{
if( array[i] < 0 || array[i] > array_len-1 )
return -1;
}
/**主算法**/
int temp=0;
for( i=0; i<array_len; i++ )
{
while( array[i] != i )
{
if( array[i] != array[array[i]] )
swap(array[i], array[array[i]], temp);
else
return array[i];
}
}
return -1; //没找着，返回-1
}
四、测试代码及结果
【题型一】的测试结果
int main()
{
printf("测试代码！
");
int* array;
int i;
array = (int*)malloc(5*sizeof(int));
printf("请输入5个数组元素：
");
for( i=0;i<5;i++ )
scanf("%d",&array[i]);
array = mark_times_apear(array,5);
for( i=0;i<5;i++ )
printf("%d ",array[i]);
return 0;
}
梦想还是要有的，万一实现了呢~~~ヾ(◍°∇°◍)ﾉﾞ~~~
————————————————
版权声明：本文为CSDN博主「qiki_tang」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qiki_tangmingwei/article/details/80109822