kos*_*tia 14 java puzzle algorithm big-o
这是一个家庭作业的问题,我已经考虑了很长一段时间,并提出了几个解决方案,但我认为存在更好的解决方案.
确定数组中是否存在仅出现一次的元素(int)的最快方法是什么？任何元素都可以出现任意次.{3,1,4,1,4,3}将返回false,而{3,1,4,1,4,1}将返回true(3出现一次).
我们只允许使用我们已经学过的东西(所有基础知识,递归,oop,搜索和排序算法,包括快速排序),因此制作哈希表不是一种选择.
到目前为止,我提出的最佳实用解决方案是使用quicksort对其进行排序然后通过它(O(nlogn)),我提出的最好的不切实际的解决方案是创建一个大的数组大小所有可能的int值,然后使用它类似于哈希表的位置(但该数组太大而无法实际实现)(O(n))
在O(n)时间内还有另一种(实用的)方法吗？
编辑:刚从TA得到答案,我听说的建议的O(n)解决方案是一个不实用的解决方案(与我建议的相同或相似),因此他们告诉我们不要使用它.我99%肯定现在最好的实际答案(没有哈希表)是O(nlogn)时间.
小智 5
您可以使用自定义的快速排序来查找不同的值,而不会在之后迭代排序的数组.
当您选择了一个数据透视值并且正在移动数组的相应部分时,如果该值与数据透镜匹配,则丢弃它并在移动数组部分后丢弃透视值,这将删除数组之前的重复项最终排序.
即:
Sorting [5, 1, 4, 1, 4, 1]
If you choose the pivot as 4, you'd end up with the 2 sub arrays being:
[1, 1, 1] and [5]
如果您的枢轴永远不会被丢弃,那么它是不同的,如果它被丢弃,则在子列表上执行相同的过程.如果子列表只有1个元素,则它是不同的.
通过这种方式,您可以更早地获取不同的值.
编辑:是的,这仍然受到O(nlogn)的限制(我想？)
| 归档时间： |
|
| 查看次数： |
4175 次 |
| 最近记录： |