Jjy*_*yKs 10 java arrays sorting algorithm
这是一个额外的学校任务,我们还没有接受任何教学,我不是在寻找完整的代码,但是一些提示可以很快.我回到家时会发布到目前为止我用Java做的事情,但这里已经有了我已经做过的事情.
因此,我们必须进行排序算法,例如将"AAABBB"排序到ABABAB.最大输入大小为10 ^ 6,所有这些都必须在1秒内完成.如果有多个答案,则按字母顺序排列的第一个答案是正确答案.我开始测试不同的算法,甚至在没有字母顺序要求的情况下对它们进行排序,只是为了看看事情是如何运作的.
第一版:
将ascii代码保存到Integer数组中,其中index是ascii代码,值是char数组中该字符出现的数量.然后我选择了2个最高的数字,并开始将它们互相垃圾邮件发送给新的字符数组,直到某个数字更高,然后我换了它.它工作得很好,但当然订单不对.
第二版:
遵循相同的想法,但停止选择最常出现的数字,并按照它们在我的数组中的顺序选择索引.运作良好,直到输入像CBAYYY.算法将其分类为ABCYYY而不是AYBYCY.当然我可以尝试为那些Y找到一些免费的位置,但在那时它开始花费太长时间.
一个有趣的问题,有一个有趣的调整.是的,这是一种排列或重新排列而不是一种排列.不,引用的问题不重复.
算法.
需要注意避免一个一个错误(奇数与偶数个输入字符).否则,只需编写代码并使其正常工作就是挑战.
请注意,有一种特殊情况,其中字符数为奇数,一个字符的频率从(半加1)开始.在这种情况下,您需要从算法中的步骤4开始,依次输出所有一个字符与其他字符交替.
另请注意,如果一个字符包含输入的一半以上,那么对于这种特殊情况,则无法解决问题.可以通过检查频率或在尾部由所有一个字符组成的执行期间预先检测这种情况.检测此案例不属于规范.
由于不需要排序,因此复杂度为O(n).每个字符都要检查两次:一次是计数,一次是加到输出.其他一切都是摊销的.