寻找出现不同频率的数

灰太狼 2022-11-14 10:22 123阅读 0赞

Assume we have a sequence that contains N numbers of type long. And we know for sure that among this sequence each number does occur exactly n times except for the one number that occurs exactly m times ( 0 < m < n ) . How do we find that number with O(N) operations and O(1) additional memory?

**Example.** We know that **n=3** and **m=2**  
 The sequence ( **N**=8 )is :5 11 5 2 11 5 2 11  
 And the right answer is **2** in this partcular case because it occurs only twice.

分析：  
题目的意思是给定一个数组，数组中的每个值都是Long型，且这堆数字是乱序的，其中有些数字会出现n次，而只有1个数字会出现m次，如何通过O(N)的时间复杂度和O(1)的利用空间找到这个数字？

对于这个例子来说，数组中的每个数为5 11 5 2 11 5 2 11 ，如何去寻找到2？  
首先转化为2进制数：

<table> 
 <thead> 
  <tr> 
   <th>数组中的元素</th> 
   <th>对应的二进制数</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>5</td> 
   <td>101</td> 
  </tr> 
  <tr> 
   <td>11</td> 
   <td>1011</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>10</td> 
  </tr> 
 </tbody> 
</table>

统一以4位二进制数表示

<table> 
 <thead> 
  <tr> 
   <th>数组中的元素</th> 
   <th>对应的二进制数</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>5</td> 
   <td>0101</td> 
  </tr> 
  <tr> 
   <td>11</td> 
   <td>1011</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>0010</td> 
  </tr> 
 </tbody> 
</table>

然后将数组中的每个数都转为2进制数，然后每位进行求和然后接着对n取余，如果余数不为0，则表示要寻找的数的二进制数中的这一位是有值的，这样最终就可以确定我们要寻找的数了。

因此对于例子来说：

<table> 
 <thead> 
  <tr> 
   <th>二进制数</th> 
   <th>数组中的数</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>0101</td> 
   <td>5</td> 
  </tr> 
  <tr> 
   <td>1011</td> 
   <td>11</td> 
  </tr> 
  <tr> 
   <td>0101</td> 
   <td>5</td> 
  </tr> 
  <tr> 
   <td>0010</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>1011</td> 
   <td>11</td> 
  </tr> 
  <tr> 
   <td>0101</td> 
   <td>5</td> 
  </tr> 
  <tr> 
   <td>0010</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>1011</td> 
   <td>11</td> 
  </tr> 
  <tr> 
   <td>每位求和对3取余的结果为0010</td> 
   <td>-</td> 
  </tr> 
 </tbody> 
</table>

因此我们找到了0010，转为十进制数即为2。

有了上面的分析，再加上限制条件：O(N)的时间复杂度和O(1)的利用空间。  
解题思路  
对于long型数据，在c中占4个字节，即32个bit，也就是二进制数的最大位数为32位，因此需要一个长度为32的临时数组用来存储数组中的每个元素转为二进制数后的每个bit位的累计和，在遍历的时候，将数组中的每个元素变为二进制数，放入这个32位的临时数组并对每位求累计和，最后遍历完数组后，将临时数组中的每个元素对n取余，然后再将该数组转为对应的十进制数，即我们要寻找的那个数据。

代码：

#include<stdio.h>
    #include<math.h>
    #define N 8
    #define SIZE 32
    int main()
    { 
        long int a[N] = { 5, 11, 5, 2, 11, 5, 2, 11};
        //int m = 2;
        int n =3;
        int result[SIZE] = { 0}; //临时数组，存放32位表示的二进制数
        long int num = 0; //要寻找的数
    
        for(int i=0; i< N; i++)
        { 
            int temp[SIZE] = { 0};
            long int t = a[i];
            int j = 0;
            //转二进制数
            while(t)
            { 
                temp[j] = t%2;
                t /= 2;
                j++;
            }
            //二进制数每位累计求和
            for(int k = 0; k<SIZE; k++)
                result[k] += temp[k];
        }
    
        //对每个二进制位取余，然后将该数组转化为对应的十进制数
        for(int i=0; i< SIZE; i++)
        { 
            result[i] = result[i] % n;
            if(result[i] != 0)
            { 
                num += pow(2, i);
            }
        }
        printf("%ld",num);
    }

参考：  
https://blog.csdn.net/zzz805/article/details/89740506