blocks|key|572790|text|听起来像是简单的计数。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|572791|为一个大小为100万的数组预留内存|ordered-list-item|572792|将所有数组值初始化为0|572793|通过整数循环。对于每一个整数i增加一个ai。|572794|输出排序序列，通过遍历数组和打印每个数字i的ai次。|572795|空间是恒定的。运行时为O(n)。|572796|entityMap^0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|P|8|@]|9|@]|A|$]]|$1|E|3|F|5|D|7|Q|8|@]|9|@]|A|$]]|$1|G|3|H|5|D|7|R|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|S|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|T|8|@]|9|@]|A|$]]|$1|M|3|-4|5|6|7|U|8|@]|9|@]|A|$]]]|N|$]]

Sounds like a straightforward counting sort.

<ol>
<li>Reserve memory for an array a of size 1 million</li>
<li>Initialize all array values to 0</li>
<li>Loop through the integers. For each integer i increment a[i] by one.</li>
<li>Output sorted sequence by walking through the array and printing each number i for a[i] times.</li>
</ol>

Space is constant. Runtime is O(n).

blocks|key|572818|text|暗示应该是，他们的范围从100万到100万。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|572819|请参阅针孔分类|offset|length|572820|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Pigeonhole_sort^0|0|3|4|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|O|8|@]|9|@$D|P|E|Q|1|R]]|A|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|A|$]]]|G|$H|$5|I|J|K|A|$L|M]]]]

The hint should be that they range from 1 to 1 million. 

See <a href="http://en.wikipedia.org/wiki/Pigeonhole_sort" rel="nofollow">pigeonhole sort</a>

blocks|key|572850|text|由于问题的大小是固定的，并且包含一个有限的实例集，所以任何排序算法都会在O(1)中终止。你应该让测试人员回到算法分析学校去。将这个问题推广到无限集合的一种可能方法是:您有一个大小为n的数组，其数字范围为0，10n。你能用O(n)分类吗？这对我来说很有意义。或者你可以用数组的大小和整数的范围来参数化这个问题，得到一些O(f(n，k))界。问题是当你在面试中遇到这样的问题时，你会怎么做？你是想猜面试官想听什么，还是说“让我重新表达你的问题”？还是你带着笑容朝出口走去？|type|unstyled|depth|inlineStyleRanges|entityRanges|data|572851|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Since the problem has fixed size and includes a finite set of instances, any sorting algorithm will terminate in O(1). You should tell the tester to go back to algorithm analysis school. One possible way to generalize this problem to an infinite set is: you have an array of size n with numbers ranging in [0, 10n]. Can you sort it in O(n)? That makes sense to me. Or you could parametrize the problem with the size of the array and the range of the integers and come up with some O(f(n,k)) bound. The problem is when you get a question like this in an interview, what do you do? Do you try to guess what the interviewer would like to hear or do you say something like "let me rephrase your question"? Or you just scoot towards the exit with a big smile?

blocks|key|572745|text|使用计数排序。只需计算所有它们(+O(n)+)，然后创建填充结果数组(+O(n)，再次)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|572746|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Use count sort. Just count all of them ( O(n) ), and then create fill the result array ( O(n), again).

blocks|key|1770814|text|您必须使用复杂度为O(n)的任何已知排序算法。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1770815|有O(n)整数排序算法吗？|offset|length|1770816|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/questions/2352313/is-there-an-on-integer-sorting-algorithm^0|0|0|D|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|O|8|@]|9|@$D|P|E|Q|1|R]]|A|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|A|$]]]|G|$H|$5|I|J|K|A|$L|M]]]]

You have to use any known sorting algorithms with complexity O(n)

<a href="https://stackoverflow.com/questions/2352313/is-there-an-on-integer-sorting-algorithm">Is there an O(n) integer sorting algorithm?</a>

So here is the question:

<blockquote>
 Suppose you have 100 thousand integers which ranges from 1 to 1 million. Please sort out the integers. The time complexity should be O(n).
</blockquote>

Anybody who shares his or her ideas is well appreciated.

Another Algorithm Job-Interview

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

以下是问题所在：假设你有10万个整数，从1到1百万不等。请把整数分类。时间复杂度应为O(n)。任何分享他或她的想法的人都会受到很好的赞赏。

问另一种算法--面试
EN

回答 5

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问另一种算法--面试EN

回答 5

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问另一种算法--面试
EN