嵌入式软件-无需排序找数字

题目

有1000个整数，每个数字都在1～200之间，数字随机排布。假设不允许你使用任何排序方法将这些整数有序化，你能快速找到从0开始的第450小的数字吗？（从小到大第450位）

示例

解答

解法一：1、不能排序

2、找从0开始的第450位小的数，注意的“从0开始”这句话。[0-450]这个区间总共有451个数，因此我们需要找的是第451位小的数

开始做题----------------------------------------------------------

可以利用hash表的特性，使用一个201大小的数组，数组的下标为数据的值，数组的值为数据出现的次数。

可以这么理解

key->代表数据，同时也是数组下标

value->代表数据出现的次数

首先给数组元素初始化为0，也就是每个数据出现的次数都是0。

接着使用循环将每个数据出现的次数添加到数组中

再利用循环将出现的次数累加，如果次数累加到450，就说明找到了第450大的数

code1

/*
1、定义一个大小为201的整型数组arr，用来存储每个数在数组numbers中出现的次数。使用memset函数将所有元素初始化为0。
2、定义一个整型变量i，用来作为循环的计数器。初始化为0。
3、使用while循环遍历数组numbers，对于每个数，将其作为arr的下标，将arr对应的元素加一，表示该数出现了一次。同时将i加一，表示下一个数。
4、重新将i赋值为1，表示从第一个数开始计算出现次数之和。
5、定义一个整型变量sum，用来累计前面的数出现的次数之和。初始化为0。
6、使用while循环遍历arr，从下标1开始，对于每个元素，将其加到sum上，然后判断sum是否大于或等于451。如果是，则跳出循环，表示找到了满足条件的数。如果不是，则继续遍历。
7、返回i，表示找到的数。
  */
int find(int* numbers, int numbersLen ) {
    // write code here
    int arr[201], i=0, sum=0; //定义一个大小为201的整型数组arr，用来存储每个数在数组numbers中出现的次数。定义一个整型变量i，用来作为循环的计数器。定义一个整型变量sum，用来累计前面的数出现的次数之和。

    //初始化数组元素
    memset(arr,0,sizeof(arr)); //使用memset函数将所有元素初始化为0。
    
    //循环添加每个数据出现的次数
    while(i < numbersLen){ //使用while循环遍历数组numbers
        arr[numbers[i]]++; //对于每个数，将其作为arr的下标，将arr对应的元素加一，表示该数出现了一次。
        i++; //同时将i加一，表示下一个数。
    }

    //循环计算次数，当次数超过451次，那就是找到了
    i=1; //重新将i赋值为1，表示从第一个数开始计算出现次数之和。
    while((sum=sum+arr[i]) < 451){ //使用while循环遍历arr，从下标1开始
        i++; //对于每个元素，将其加到sum上，并将i加一。
    }
    
    return i; //返回i，表示找到的数。
}

code2

解法二：因为知道每个数字的大小：1~200，所以无论序列有多少个数字，可以根据一个200行的表，然后统计所有数字出现的频率。

这个思路在硬件设计上常见，即用数字的值代表查表的地址。

/*
1、定义一个大小为201的整型数组table，用来存储每个数在数组numbers中出现的次数。初始化为0。
2、遍历数组numbers，对于每个数，将其作为table的下标，将table对应的元素加一，表示该数出现了一次。
3、定义一个整型变量acc，用来累计前面的数出现的次数之和。初始化为0。
4、遍历table，从下标1开始，对于每个元素，将其加到acc上，然后判断acc是否大于或等于451。如果是，则返回当前的下标，表示找到了满足条件的数。如果不是，则继续遍历。
5、如果遍历完table都没有找到满足条件的数，则返回0。
*/
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param numbers int整型一维数组
 * @param numbersLen int numbers数组长度
 * @return int整型
 */
int find(int* numbers, int numbersLen ) {
    // write code here
    int table[201] = {0}; //定义一个大小为201的整型数组table，用来存储每个数在数组numbers中出现的次数。初始化为0。
    for (int i = 0; i < numbersLen; i++) {
        table[numbers[i]]++; //遍历数组numbers，对于每个数，将其作为table的下标，将table对应的元素加一，表示该数出现了一次。
    }

    int acc = 0; //定义一个整型变量acc，用来累计前面的数出现的次数之和。初始化为0。
    for (int i = 1; i < 201; i++) {
        acc += table[i]; //遍历table，从下标1开始，对于每个元素，将其加到acc上。
        if (acc >= 451) return i; //判断acc是否大于或等于451。如果是，则返回当前的下标，表示找到了满足条件的数。
    }
    return 0; //如果遍历完table都没有找到满足条件的数，则返回0。
}