小编Ani*_*tti的帖子

只有素数因子为2,3或5的数字称为丑陋数字.

例:

1,2,3,4,5,6,8,9,10,12,15 ......

1可以被认为是2 ^ 0.

我正在努力寻找第n个难看的数字.请注意,当n变大时,这些数字非常稀疏地分布.

我写了一个简单的程序来计算给定数字是否丑陋.对于n> 500 - 它变得超级慢.我尝试使用memoization - 观察:ugly_number*2,ugly_number*3,ugly_number*5都很难看.即便如此,它也很慢.我尝试使用log的一些属性 - 因为这会将这个问题从乘法减少到另外 - 但是,运气不大.想与大家分享这个.任何有趣的想法？

使用类似于"Eratosthenes的筛子"的概念(感谢Anon)

    for (int i(2), uglyCount(0); ; i++) {
            if (i % 2 == 0)
                    continue;
            if (i % 3 == 0)
                    continue;
            if (i % 5 == 0)
                    continue;
            uglyCount++;
            if (uglyCount == n - 1)
                    break;
    }

我是第n个难看的数字.

即便这样也很慢.我想找到第1500个难看的数字.

给定具有m行和n列的矩阵,每个列都被排序.如何有效地整理整个矩阵？

我知道一个在O(mn log(min(m,n))中运行的解决方案.我正在寻找更好的解决方案.

我知道的方法一次基本上需要2行/列并应用合并操作.

这是一个例子:

[[1,4,7,10],

 [2,5,8,11],

 [3,6,9,12]]

是输入martix,它对每一行和每列进行排序.

预期产出是:

[1,2,3,4,5,6,7,8,9,10,11,12]

另一个例子:

[[1, 2, 3, 3, 4, 5, 6, 6, 7, 7],

 [1, 2, 4, 6, 7, 7, 8, 8, 9,10],

 [3, 3, 4, 8, 8, 9,10,11,11,12],

 [3, 3, 5, 8, 8, 9,12,12,13,14]]

有人能想到用于确定元素列表中的多数元素的线性时间算法吗？算法应该使用O(1)空间.

如果n是列表的大小,则多数元素是至少出现一次的元素ceil(n / 2).

[Input] 1, 2, 1, 1, 3, 2

[Output] 1

[编者注]这个问题存在技术错误.我宁愿离开它,以免破坏接受的答案的措辞,纠正错误并讨论原因.请检查接受的答案.

我正在使用networkx(一个python图形绘图包)http://networkx.lanl.gov/index.html进行我的一个项目.虽然networkx非常酷,但由于交叉边缘的数量,显示功能很糟糕.有没有办法最小化图中的交叉边？我的意思是一种算法,它可以以一种最小化交叉边缘的方式对节点进行排序？

我们能否证明可以从其有序和级别顺序遍历中明确地构造二叉树？

我正在考虑一个关于级别数量的归纳证明.

基本情况:1或2级的树木.这些案件很清楚.

假设这适用于具有l级别的树.也就是说:可以从其有序和水平顺序遍历中明确地构造具有l级的二叉树.

归纳案例:证明这适用于l + 1级别的树木.在这种情况下不清楚如何进行.任何帮助将不胜感激.

有些人可能在这个可爱的文章都有所涉猎- http://igoro.com/archive/quicksort-killer/ \

真正有趣的是他如何修复快速排序以在O(N log N)中对定义的对手执行.

快速排序可以选择中间元素作为每一步的枢轴,从而始终将输入序列的完美分割为两半.可以在O(N)运行时间确定性地找到中位数,因此总运行时间总是O(N log N).

我的问题是,线性时间中值查找算法最终不会使用相同的比较函数并以O(N ^ 2)而不是O(N)执行？

编辑:

确切地说:我质疑基于分区的中值选择算法的复杂性,该算法使用类似于快速排序的策略,它将使用与快速排序使用的相同的比较功能.如何在这个对手的O(N)中运作？

考虑使用malloc()在碎片堆中分配x个字节的内存.假设堆有多个大小大于x字节的连续位置.

哪个是最好的(导致最少的堆浪费)启发式选择以下位置？

1. 选择大于x字节的最小位置.
2. 选择大于x字节的最大位置.

我的直觉是比x字节大的最小位置.我不确定哪种是最好的.

不,这不是任何转让问题.我正在读这个怎么做malloc()和free()工作？这看起来像是一个很好的跟进问题.

在C中填充结构有什么用？

存在一系列递增的数字,其中包含相同数量的二进制1.给定n(系列中每个数字中设置的1位数)写入算法或C程序以找到系列中的第n个数字.

我在互联网上发现了这个问题,我认为答案只是(((1 <<(n + 1)) - 1)&~2).不是吗？我发现了一些可怕的程序来计算答案.