白话经典算法系列之十六 “基数排序”之数组中缺失的数字

小灰灰 2023-06-18 07:58 12阅读 0赞

首先看看题目要求：

给定一个无序的整数数组，怎么找到第一个大于0，并且不在此数组的整数。比如\[1,2,0\]返回3，\[3,4,-1,1\]返回2，\[1, 5, 3, 4, 2\]返回6，\[100, 3, 2, 1, 6,8, 5\]返回4。要求使用O(1)空间和O(n)时间。

这道题目初看没有太好的思路，但是借鉴下《[白话经典算法系列之十  一道有趣的GOOGLE面试题][_GOOGLE]》这篇文章，我们不发现使用“基数排序”正好可以用来解决这道题目。

以\{1, 3, 6, -100, 2\}为例来简介这种解法：

从第一个数字开始，由于a\[0\]=1，所以不用处理了。

第二个数字为3，因此放到第3个位置（下标为2），交换a\[1\]和a\[2\]，得到数组为\{1, 6, 3, -100, 2\}。由于6无法放入数组，所以直接跳过。

第三个数字是3，不用处理。

第四个数字是-100，也无法放入数组，直接跳过。

第五个数字是2，因此放到第2个位置（下标为1），交换a\[4\]和a\[1\]，得到数组为\{1, 2, 3, -100, 6\}，由于6无法放入数组，所以直接跳过。  
此时“基数排序”就完成了，然后再从遍历数组，如果对于某个位置上没该数，就说明数组缺失了该数字。如\{1, 2, 3, -100, 6\}缺失的就为4。

这样，通过第i个位置上就放i的“基数排序”就顺利的搞定此题了。

代码也非常好写，不过在交换两数时要注意判断下两个数字是否相等，不然对于像\{1, 1, 1\}这样的数据会出现死循环。

完整的代码如下：

// 【白话经典算法系列之十六】“基数排序”之数组中缺失的数字
    //  by MoreWindows( http://blog.csdn.net/MoreWindows ) 
    //  欢迎关注http://weibo.com/morewindows
    #include <stdio.h>
    void Swap(int &a, int &b)
    {
      int c = a;
      a = b;
      b = c;
    }
    int FindFirstNumberNotExistenceInArray(int a[], int n)
    {
      int i;
      // 类似基数排序，当a[i]>0且a[i]<N时保证a[i] == i + 1
      for (i = 0; i < n; i++)
        while (a[i] > 0 && a[i] <= n && a[i] != i + 1 && a[i] != a[a[i] - 1])
            Swap(a[i], a[a[i] - 1]);
      // 查看缺少哪个数
      for (i = 0; i < n; i++)
        if (a[i] != i + 1)
          break;
      return i + 1;
    }
    void PrintfArray(int a[], int n)  
    {  
      for (int i = 0; i < n; i++)  
        printf("%d ", a[i]);  
      putchar('\n');  
    } 
    int main()
    {
      printf("    【白话经典算法系列之十六】“基数排序”之数组中缺失的数字\n");
      printf(" -- by MoreWindows( http://blog.csdn.net/MoreWindows ) --\n");
      printf(" -- http://blog.csdn.net/morewindows/article/details/12683723 -- \n\n");
     
      const int MAXN = 5;
      //int a[MAXN] = {1, 2, 3, 4, 7}; 
      //int a[MAXN] = {1, 3, 5, 4, 2};
      int a[MAXN] = {2, -100, 4, 1, 70};
      //int a[MAXN] = {2, 2, 2, 2, 1};
      PrintfArray(a, MAXN);
      printf("该数组缺失的数字为%d\n", FindFirstNumberNotExistenceInArray(a, MAXN));
      return 0;
    }

运行结果如下图所示：

![SouthEast][]

[_GOOGLE]: https://blog.csdn.net/rocling/article/details/103333553
[SouthEast]: https://img-blog.csdn.net/20131013194529234?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvTW9yZVdpbmRvd3M=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast