这是场景.
我得到一个整数数组'A'.数组的大小不固定.我应该写的函数可以用一个只有几个整数的数组调用一次,而另一个时间,甚至可能包含数千个整数.另外,每个整数不需要包含相同数量的数字.
我应该对数组中的数字进行"排序",使得结果数组具有以字典方式排序的整数(即,它们基于它们的字符串表示进行排序.这里"123"是123的字符串表示).请注意,输出应仅包含整数,而不是它们的字符串等效项.
例如:如果输入是:
[12 | 2434 | 23 | 1 | 654 | 222 | 56 | 100000]
那么输出应该是:
[1 | 100000 | 12 | 222 | 23 | 2434 | 56 | 654]
我的初始方法:我将每个整数转换为其字符串格式,然后在其右侧添加零以使所有整数包含相同数量的数字(这是一个混乱的步骤,因为它涉及跟踪等使得解决方案非常低效)然后做了基数排序.最后,我删除了填充的零,将字符串转换回它们的整数并将它们放入生成的数组中.这是一个非常低效的解决方案.
我一直认为解决方案不需要填充等,并且有一个简单的解决方案,你只需要以某种方式处理数字(一些位处理？)来获得结果.
您能想到的空间最有效的解决方案是什么？浪费时光？
如果你要提供代码,我更喜欢Java或伪代码.但如果这不适合你,任何这样的语言应该没问题.
我在面试问题主题上遇到了这个问题.这是一个问题:
给定两个整数数组A [1..n]和B [1..m],找到A中包含B的所有元素的最小窗口.换句话说,找到一对<i,j>,使得A [i ..j]包含B [1..m].
如果A不包含B的所有元素,那么i,j可以返回-1.A中的整数不必与B中的整数相同.如果有多个最小窗口(不同,但具有相同的大小),那么它足以返回其中一个.
例如:A [1,2,5,11,2,6,8,24,101,17,8]和B [5,2,11,8,17].该算法应该返回i = 2(A中的索引为5)和j = 9(A中的索引为17).
现在我可以想到两种变化.
我们假设B有重复.
这种变化不考虑每个元素在B中出现的次数.它只检查B中出现的所有唯一元素,并找到满足上述问题的A中最小的对应窗口.例如,如果A [1,2,4,5,7]和B [2,2,5],这个变化并不打扰B中有两个2,只检查A中B的唯一整数即因此,返回i = 1,j = 3.
这种变化考虑了B中的重复.如果B中有两个2,那么它也希望在A中看到至少两个2.如果不是,则返回-1,-1.
当你回答时,请告诉我你要回答的变体.伪代码应该做.如果计算它很棘手,请提及空间和时间复杂度.提及您的解决方案是否假设数组索引也从1或0开始.
提前致谢.
我有两个非常大的文件(它们都不适合内存).每个文件在每一行都有一个字符串(其中没有空格,长度为99/100/101个字符).
更新:字符串不是任何排序顺序.
Update2:我在Windows上使用Java.
现在我想弄清楚找出两个文件中出现的所有字符串的最佳方法.
我一直在考虑使用外部合并排序来对两个文件进行排序然后进行比较,但我不确定这是否是最好的方法.由于字符串大多数都是相同的长度,我总是想知道为每个字符串计算某种哈希是否是个好主意,因为这样可以使字符串之间的比较更容易,但那意味着我必须存储哈希值计算我到目前为止从文件中遇到的字符串,以便稍后在将它们与其他字符串进行比较时可以使用它们.我无法确定最佳方式.我在寻找你的建议.
当您提出解决方案时,如果有超过2个文件并且必须计算出所有文件中出现的字符串,请说明解决方案是否有效.