昨天我们留了一道题目“给你一个整型数组,里面出现的数在[0-100] 之间,能用最优化的方法帮我排序吗”。
这是一道排序算法题,我们学过很多排序的算法。不一样的是,它给定一个额外的条件,数组里的每个数字都在1-100之间。如果我们采取传统的排序算法,这个条件我们好像用不上。大家在面试的时候如果发现有条件没有用上,基本上我们给出的算法可能不是最优的,或者我们没有解决它最原始的需求。举个例子{50, 46, 50, 0, 100,0} 这个数组中,我们一眼就能看出来 0 有两个, 46有一个,50有两个,100有一个,我们再把他们拼接起来,我们就会得到 {0,0, 46, 50, 50,100}。
在上面的分析中我们能够总结出来,我们人工去排序的时候涉及到了两个重要的步骤。1:统计0 - 100 之间每一个数出现的次数: 2: 从0 - 100 的顺序按照他们出现的次数拼接出来。所以现在我们需要解决的问题如何方便计数了。申明一个数字,长度为101,假设50出现了一次,我们就把该数组中下标为50的位置加上1. 全部计数完了,我们再扫描这个数字,将结果写回。
我们现在看一下它的复杂度,我们扫描了原数组一次,又扫描了计数数组一次,所以我们的复杂度是O(n). 这里大家也发现,我们这道题中体现了一个原则,用空间换时间。
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 ++;
}
}
那我们就直接上代码啦。
/// <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 + " " );
}
}
我们得到的结果:
大功告成了哈。欢迎大家关注我的公众号,还有我的系列专题课程
大家有什么更好的解法,也欢迎讨论哈。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。