求循环数组中子序列的第k个最小数

Question

你好，我正在尝试从IEEEXtreme 2014解决这个问题：

给你N个循环排列的整数。有N种方法可以拾取长度为M（M）的连续子序列

我的方法是首先创建一个排序数组列表，将新输入插入正确的位置。我将前M个整数添加到列表中。记录第K个最小值。然后我继续删除最旧的整数并将下一个整数添加到列表中，并将新的第K个值与旧的值进行比较。这是我的排序数组列表。

class SortedArrayList extends ArrayList {  
    public void insertSorted(int value) {        
        for (int i = size()-1; i >= 0; i--){
            if( value - (Integer)get(i)>=0){            
                    add(i+1,new Integer(value));
                    return;
            }
        }
        add(0,new Integer(value));
    }
}

我认为这种蛮力方法效率不高，但还不能想出任何想法。你知道更好的解决方案吗？谢谢

Answer 1

对于圆形阵列的问题，更优雅的解决方案是简单地使用模。因此，如果您只是在寻找模拟圆形阵列的解决方案，我建议如下：

int n = somevalue;//the startingpoint of the subsequence
int m = someothervalue;//the index in the subsequence

int absolute_index = (n + m) % N;

其中N是序列中元素的总数。

提高效率的下一步是存储第k个值的索引。这样，您只需每隔M步（最坏情况）计算一个新的K值，然后只需每隔一步将其与一个新值进行比较。但我会把这个留给你；）

Answer 2

以下是一个更有效的解决方案：

>

让我们摆脱循环以使事情更简单。我们可以通过将给定数组附加到它本身来做到这一点。

我们可以假设输入中的所有数字都是唯一的。如果不是这样，我们可以使用一对（元素，位置）来代替每个元素。

让我们对给定的数组进行排序。现在，我们将对答案使用二进制搜索（即排序的全局数组中所有子数组中第k个最小元素的位置）。

如何检查固定候选x至少与k最小数字一样大？让我们用1标记小于或等于x的数字的所有位置，其余的用0。现在我们只需要检查是否有一个长度M的子数组至少包含k。我们可以使用滚动和在线性时间内完成。

时间复杂度为：O（N log N）用于对输入进行排序O（N log N）用于对答案进行二进制搜索（有O（log N）检查，每个检查都是在线性时间内完成的，如4所述）。因此，总时间复杂度为O（N log N）。

P、 我可以想到其他几个具有相同时间复杂性的解决方案，但这一个似乎是实现最简单的解决方案（它不需要任何自定义数据结构）。