如何通过规模组编号

Question

我ň不同的数字，我想将它们整理到ķ群体，例如，任何数量组1组2小于任意数量较小的第2组，和任何人比组3中的任何人都要多，直到组k（数字不必在每个组内排序）。我被要求设计一个运行在O（n log k）的算法，但我只能拿出O（n^2）。

我该怎么做？

Answer 1

注意的问题陈述是到n 不同号码分成k个组。如果下面的维基链接中提到重复，这会变得更加复杂。

任何能够确定小于O（n log（k））复杂度的第k个最小元素的过程可以被使用k-1次以产生与k个组之间的边界相对应的元素阵列。然后可以在该阵列上进行一次通过，对边界阵列进行二进制搜索以将阵列分成具有O（nlog（k））复杂度的k个组。然而，似乎至少有一种算法找到第k个最小的元素也划分了数组，因此单独可以用来创建k个组。

使用具有最坏情况时间O（n）的选择算法的无序部分排序是可能的。维基链接：

http://en.wikipedia.org/wiki/Selection_algorithm

http://en.wikipedia.org/wiki/Selection_algorithm#Unordered_partial_sorting

http://en.wikipedia.org/wiki/Quickselect

http://en.wikipedia.org/wiki/Median_of_medians

http://en.wikipedia.org/wiki/Soft_heap#Applications

Answer 2

您可以通过修改Bucket排序算法来实现这一点，下面我已经包含了一个JavaScript实现，关于源代码的更多细节，请参见Github。此实现使用16个存储桶，您将不得不修改它以允许存储桶k，并且您可以省略存储桶本身的排序。一种方法是使用2^p存储桶，其中p是满足2^p < n的最小整数。该算法将在Ø运行（N日志K）

// Copyright 2011, Tom Switzer 
 
// Under terms of ISC License: http://www.isc.org/software/license 
 

 
/** 
 
* Sorts an array of integers in linear time using bucket sort. 
 
* This gives a good speed up vs. built-in sort in new JS engines 
 
* (eg. V8). If a key function is given, then the result of 
 
* key(a[i]) is used as the integer value to sort on instead a[i]. 
 
* 
 
* @param a A JavaScript array. 
 
* @param key A function that maps values of a to integers. 
 
* @return The array a. 
 
*/ 
 
function bsort(a, key) { 
 
    key = key || function(x) { 
 
    return x 
 
    }; 
 
    var len = a.length, 
 
    buckets = [], 
 
    i, j, b, d = 0; 
 
    for (; d < 32; d += 4) { 
 
    for (i = 16; i--;) 
 
     buckets[i] = []; 
 
    for (i = len; i--;) 
 
     buckets[(key(a[i]) >> d) & 15].push(a[i]); 
 
    //This implementation uses 16 buckets, you will need to modify this 
 
    for (b = 0; b < 16; b++) 
 
     //The next two lines sort each bucket, you can leave it out 
 
     for (j = buckets[b].length; j--;) 
 
     a[++i] = buckets[b][j]; 
 
    } 
 
    return a; 
 
} 
 

 

 
var array = [2, 4, 1, 5, 3]; 
 

 
$('#result').text(bsort(array, function(x) { 
 
    return x 
 
}));

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> 
 
<div id="result"></div>

Answer 3

使用与快速排序功能分区K-选择算法 - QuickSelect。
为简单起见，让我们的K是2的幂。
第一阶段我们分割N个元素，它需要O（N）〜p * N时间，其中p是一些常数
在第二阶段我们递归地生成2个N/2元素的分区，它需要2 * p * N/2 = p * N时间。
在第三阶段，我们制作了4个N/4个元素的分区，它需要N次4 * p N/4 = p。
...
在最后阶段，我们制作N个K个元素的K个分区，它需要K * p * N/K = p * N个时间。

注有日志（K）的阶段，所以总时间是log（K）* P * N = O（N *日志（K）

Answer 4

感谢您所有的帮助，基本上是quickselect（或任何在线性时间内找到第k个统计量的线性时间排序算法就足够了），在运行k-1次之后，我们对原始数组进行二分法搜索，将元素拆分成组，得到O（nlog k） 。

另外，如果你不想做一个二进制搜索，在quickselect，你也可以单独的元素，并找到在每个子集的统计！@rcgldr，@MBo感谢您的想法！