温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

计数排序 - 算法数据结构面试分享(五)

发布时间:2020-06-05 08:10:33 来源:网络 阅读:615 作者:高晓明01 栏目:软件技术

数组排序问题 - 计数排序

昨天我们留了一道题目“给你一个整型数组,里面出现的数在[0-100] 之间,能用最优化的方法帮我排序吗”。

1. 确保我们理解了问题,并且尝试一个例子,确认理解无误。

这是一道排序算法题,我们学过很多排序的算法。不一样的是,它给定一个额外的条件,数组里的每个数字都在1-100之间。如果我们采取传统的排序算法,这个条件我们好像用不上。大家在面试的时候如果发现有条件没有用上,基本上我们给出的算法可能不是最优的,或者我们没有解决它最原始的需求。举个例子{50, 46, 50, 0, 100,0} 这个数组中,我们一眼就能看出来 0 有两个, 46有一个,50有两个,100有一个,我们再把他们拼接起来,我们就会得到 {0,0, 46, 50, 50,100}。

2. 想想你可以用什么方法解决问题,你会选择哪一种,为什么?

在上面的分析中我们能够总结出来,我们人工去排序的时候涉及到了两个重要的步骤。1:统计0 - 100 之间每一个数出现的次数: 2: 从0 - 100 的顺序按照他们出现的次数拼接出来。所以现在我们需要解决的问题如何方便计数了。申明一个数字,长度为101,假设50出现了一次,我们就把该数组中下标为50的位置加上1. 全部计数完了,我们再扫描这个数字,将结果写回。
我们现在看一下它的复杂度,我们扫描了原数组一次,又扫描了计数数组一次,所以我们的复杂度是O(n). 这里大家也发现,我们这道题中体现了一个原则,用空间换时间。

3. 解释你的算法和实现的方法

计数部分:扫描原数组, 在index数组中找到对应的位置
int[] indexArray = new int[100];
foreach(var e in inputArray)
{
  indexArray[e] ++;
}
合并数组部分
int count = 0;
for(int index = 0; index < indexArray.Length; index++)
{
if(indexArray[index] > 0 ) //说明index的数字出现过,我们需要拼接起来,出现了几次我们就加几个数
 {
 inputArray[count] = index;
 count ++; 
}
}

4. 写代码的时候,记住,一定要解释你现在在干什么

那我们就直接上代码啦。

/// <summary>  
       /// 给数组排序,该数组里的值在0-100之间  
       /// </summary>  
       /// <param name="array"></param>  
       public static void IndexSort(int[] array)  
       {  
           int[] indexArray = new int[101];  

           for (var index = 0; index < indexArray.Length; index++)  
           {  
               indexArray[index] = 0;  
           }  

           foreach (var e in array)  
           {  
               indexArray[e]++;  
           }  

           int count = 0;  
           for (int index = 0; index < indexArray.Length; index++)  
           {  
               if (indexArray[index] > 0)  
               {  
                   for (int elementCount = 0; elementCount < indexArray[index]; elementCount++)  
                   {  
                       array[count++] = index;  
                   }  
               }  
           }       
       }  

大家有没有发现,上面的代码其实可以优化,会体现你的基本功哦。要装逼的话可以和面试官提出来的哦。int的默认值是0,所以我们没有必要扫描它一遍给它赋个默认值了。所以这段代码是多余的:

for (var index = 0; index < indexArray.Length; index++)  
{  
   indexArray[index] = 0;  
}  

我们来测试一下这个方法:

static void Main(string[] args)  
  {  
      int[] array = new int[] { 100, 8, 0, 7, 0, 34 };  

      IndexSort(array);  

      foreach(var e in array)  
      {  
          Console.Write(e + " " );  
      }  
  }  

5. Workthrough

6. 修复缺陷

我们得到的结果:
计数排序 - 算法数据结构面试分享(五)

大功告成了哈。欢迎大家关注我的公众号,还有我的系列专题课程


  • 视频教程
  • 数据结构与算法
  • 经典算法面试题辅导
  • 排序专题讲解
  • 链表专题讲解

大家有什么更好的解法,也欢迎讨论哈。

计数排序 - 算法数据结构面试分享(五)

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI