A是一个从整数1到n随机顺序的数组.

我需要在至少日志时间内随机访问i第一个元素的第一个最大元素j.

到目前为止我所提出的是一个n x n矩阵M,其中(i, j)位置中的元素是i第一个中最大的元素j.这给了我恒定的随机访问,但需要n^2存储.

按构造,M按行和列排序.此外,每列与其邻居的区别在于单个值.

任何人都可以提出一个方法来压缩M到n log(n)空间或更好,具有log(n)或更好的随机存取时间？

我遇到了一个有趣的编程问题,我似乎无法制定解决方案.假设你有N种不同颜色的K球.您必须将所有球分成尽可能多的组,这样两个组就不会相同.(如果每组颜色的球数相同,则认为两组相同.)您可以制作的最大组数是多少？

约束:1 <= K <= 50,1 <= N <= 14

澄清:我们想要一个算法,它接受一个整数数组> = 1.数组的大小为N,它包含的值之和为K.算法应返回最大组数.

关于这个问题的算法方法的任何想法？

我正在考虑按字典顺序排列0,...,n-1的所有排列.我给了两个等级,i和j,并且要求找到将第i个置换应用于第j个置换所产生的置换的等级.

n = 3的几个例子:

p(3)= [1,2,0],p(4)= [2,0,1],结果= [0,1,2],秩= 0

给定i = j = 4,我们得到[2,0,1]应用于它自己是[1,2,0],秩= 3.

到目前为止我得出的结论是:我通过Lehmer代码将等级转换为各自的排列,计算所需的排列,并通过Lehmer代码转换回排名.

任何人都可以建议一种方法从其他两个等级获得所需排列的排名,而不必实际计算排列？存储n!XN!数组不是一个选项.

-edit-请注意,如果其他一些命令可以实现这一点,我就不会遵循词典顺序.

-edit-这是n!由n!n = 3和4的网格,用于词典排名.将行i索引到列j以获取输出.请注意,n = 3网格与n = 4网格的左上角相同.

00|01|02|03|04|05|
01|00|03|02|05|04|
02|04|00|05|01|03|
03|05|01|04|00|02|
04|02|05|00|03|01|
05|03|04|01|02|00|

00|01|02|03|04|05|06|07|08|09|10|11|12|13|14|15|16|17|18|19|20|21|22|23|
01|00|03|02|05|04|07|06|09|08|11|10|13|12|15|14|17|16|19|18|21|20|23|22|
02|04|00|05|01|03|08|10|06|11|07|09|14|16|12|17|13|15|20|22|18|23|19|21|
03|05|01|04|00|02|09|11|07|10|06|08|15|17|13|16|12|14|21|23|19|22|18|20|
04|02|05|00|03|01|10|08|11|06|09|07|16|14|17|12|15|13|22|20|23|18|21|19|
05|03|04|01|02|00|11|09|10|07|08|06|17|15|16|13|14|12|23|21|22|19|20|18|
06|07|12|13|18|19|00|01|14|15|20|21|02|03|08|09|22|23|04|05|10|11|16|17|
07|06|13|12|19|18|01|00|15|14|21|20|03|02|09|08|23|22|05|04|11|10|17|16|
08|10|14|16|20|22|02|04|12|17|18|23|00|05|06|11|19|21|01|03|07|09|13|15|
09|11|15|17|21|23|03|05|13|16|19|22|01|04|07|10|18|20|00|02|06|08|12|14|
10|08|16|14|22|20|04|02|17|12|23|18|05|00|11|06|21|19|03|01|09|07|15|13|
11|09|17|15|23|21|05|03|16|13|22|19|04|01|10|07|20|18|02|00|08|06|14|12|
12|18|06|19|07|13|14|20|00|21|01|15|08|22|02|23|03|09|10|16|04|17|05|11|
13|19|07|18|06|12|15|21|01|20|00|14|09|23|03|22|02|08|11|17|05|16|04|10|
14|20|08|22|10|16|12|18|02|23|04|17|06|19|00|21|05|11|07|13|01|15|03|09|
15|21|09|23|11|17|13|19|03|22|05|16|07|18|01|20|04|10|06|12|00|14|02|08|
16|22|10|20|08|14|17|23|04|18|02|12|11|21|05|19|00|06|09|15|03|13|01|07|
17|23|11|21|09|15|16|22|05|19|03|13|10|20|04|18|01|07|08|14|02|12|00|06|
18|12|19|06|13|07|20|14|21|00|15|01|22|08|23|02|09|03|16|10|17|04|11|05|
19|13|18|07|12|06|21|15|20|01|14|00|23|09|22|03|08|02|17|11|16|05|10|04|
20|14|22|08|16|10|18|12|23|02|17|04|19|06|21|00|11|05|13|07|15|01|09|03|
21|15|23|09|17|11|19|13|22|03|16|05|18|07|20|01|10|04|12|06|14|00|08|02|
22|16|20|10|14|08|23|17|18|04|12|02|21|11|19|05|06|00|15|09|13|03|07|01|
23|17|21|11|15|09|22|16|19|05|13|03|20|10|18|04|07|01|14|08|12|02|06|00|

以下是n = 4的事实.为了紧凑,我把最后一个数字(总是为零)留下了.

000|001|010|011|020|021|100|101|110|111|120|121|200|201|210|211|220|221|300|301|310|311|320|321|
001|000|011|010|021|020|101|100|111|110|121|120|201|200|211|210|221|220|301|300|311|310|321|320|
010|020|000|021|001|011|110|120|100|121|101|111|210|220|200|221|201|211|310|320|300|321|301|311|
011|021|001|020|000|010|111|121|101|120|100|110|211|221|201|220|200|210|311|321|301|320|300|310|
020|010|021|000|011|001|120|110|121|100|111|101|220|210|221|200|211|201|320|310|321|300|311|301|
021|011|020|001|010|000|121|111|120|101|110|100|221|211|220|201|210|200|321|311|320|301|310|300|
100|101|200|201|300|301|000|001|210|211|310|311|010|011|110|111|320|321|020|021|120|121|220|221|
101|100|201|200|301|300|001|000|211|210|311|310|011|010|111|110|321|320|021|020|121|120|221|220|
110|120|210|220|310|320|010|020|200|221|300|321|000|021|100|121|301|311|001|011|101|111|201|211|
111|121|211|221|311|321|011|021|201|220|301|320|001|020|101|120|300|310|000|010|100|110|200|210|
120|110|220|210|320|310|020|010|221|200|321|300|021|000|121|100|311|301|011|001|111|101|211|201|
121|111|221|211|321|311|021|011|220|201|320|301|020|001|120|101|310|300|010|000|110|100|210|200|
200|300|100|301|101|201|210|310|000|311|001|211|110|320|010|321|011|111|120|220|020|221|021|121|
201|301|101|300|100|200|211|311|001|310|000|210|111|321|011|320|010|110|121|221|021|220|020|120|
210|310|110|320|120|220|200|300|010|321|020|221|100|301|000|311|021|121|101|201|001|211|011|111|
211|311|111|321|121|221|201|301|011|320|021|220|101|300|001|310|020|120|100|200|000|210|010|110|
220|320|120|310|110|210|221|321|020|300|010|200|121|311|021|301|000|100|111|211|011|201|001|101|
221|321|121|311|111|211|220|320|021|301|011|201|120|310|020|300|001|101|110|210|010|200|000|100|
300|200|301|100|201|101|310|210|311|000|211|001|320|110|321|010|111|011|220|120|221|020|121|021|
301|201|300|101|200|100|311|211|310|001|210|000|321|111|320|011|110|010|221|121|220|021|120|020|
310|210|320|110|220|120|300|200|321|010|221|020|301|100|311|000|121|021|201|101|211|001|111|011|
311|211|321|111|221|121|301|201|320|011|220|021|300|101|310|001|120|020|200|100|210|000|110|010| …

给定n个非负整数的无序列表(不保证分布或重复),我希望能够给出一个可能不在列表中的整数,并且使用列表中至少那么大的整数来响应.我有n ^ 2预处理时间,最多n*log(n)存储.这可能吗？

我的不太好的解决方案是二进制搜索(log n time,constant space).

在地图中存储所有可能查询的地图会占用太多存储空间.

编辑:需要对输入进行一些假设的部分解决方案,例如整数的分布或最大大小,也很有用.

编辑:这被称为前任/后继问题.有一篇Beame&Fich的论文,他们构建了一个数据结构,它存储来自O(n)空间中大小为N的宇宙的n个整数元素集,并在O中执行前导查询(min {(log log N)/(log) log log N),sqrt(log n /(log log n))})时间.

http://homes.cs.washington.edu/~beame/papers/stocpred.pdf

编辑 - 赏金:今天早上的答案都不是我正在寻找的.N没有界限.整数不一定低于32位.最大元素可能比元素数量大得多.我假设没有分配输入.在现有的答案中,我接受了Coffin的赏金,因为它涵盖了我确实有分布的相对较大的问题子集.

我最近碰巧想到了 JavaScript 中的对象属性访问时间，并遇到了这个问题，它似乎合理地表明它应该是常数时间。这也让我想知道对象属性键长度是否有限制。显然现代浏览器支持长达 2^30 的密钥长度，这对于哈希函数来说似乎相当不错。那说，

• 有人知道JS引擎使用的哈希函数类型吗？

• 是否可以通过实验创建 JavaScript 属性访问器的冲突？

给定一组左节点和右节点，以及它们之间的边（二分图），我需要支持从左节点集到连接到左侧任何内容的右节点子集的快速查找。

如果图形非常稀疏或密集，这很容易。下面是一个示例邻接表实现，它将支持connected_endpoints()稀疏图上的快速调用。O(len(input) * len(result))然而，对于中等数量的连接，尽管涉及的数据大小表明可能存在解决方案，但中间计算看起来像是这样O(len(input) + len(result))。

是否存在一种数据结构可以相对快速地支持这 3 个操作（或类似的操作）——添加/删除可能为 O(1)，连接边搜索为 O(in+out)，给出或采用多对数因子？

from typing import *
from collections import defaultdict

A = TypeVar('A')
B = TypeVar('B')

class Graph(Generic[A, B]):
    def __init__(self):
        self.edges = defaultdict(set)
    
    def set_edge(self, start: A, end: B):
        """Desired: Amortized O(1)"""
        self.edges[start].add(end)
    
    def unset_edge(self, start: A, end: B):
        """Desired: Amortized O(1)"""
        s = self.edges[start]
        s.discard(end)
        if not s:
            self.edges.pop(start, None)

    def connected_endpoints(self, start: Set[A]) -> Set[B]:
        """Desired: Amortized O(len(start) + len(<return>))"""
        empty = …

一组整数作为输入给出。您必须返回该集合的子集，以便该子集的均值 - 中位数是最大值。

示例 1

输入

{1,2,3,4} 

输出

{1,2,4}

示例 2

输入

{1,2,2,3,3}

输出

{2,2,3}

几天前我在系统设计面试中遇到了这个问题。我将省略无关的部分，以专注于问题的核心部分。事情是这样的。

假设我们有一组 k,v 对，键是字符串，值是整数。我们可以假设有一组固定的键（例如k1，k2，...，kn）。有一些代理将这些 k,v 对连续推送到系统中，就像流一样。我们需要做的就是将所有传入对的当前值添加到旧值。

让我们举个例子。在时间t0，我们假设我们有以下 kv 对。

k1: 100
k3: 200

此时t1，有两对传入。k2: 50, k3: 150. 因此，在 时t1，系统的状态为：

k1: 100
k2: 50
k3: 350

目标是给出在周期性间隔内具有最大值的密钥。我想不出任何算法可以比 max-heapify 提供更好的运行时间。我想到构建一个最大堆，然后在每个新数据出现时更新它。对于每次更新，heapify()将花费最log(n)长时间。在每次调用时，我们都可以返回堆的根。但还有比这更好的解决方案吗？

我有一个约瑟夫问题变体的问题。其描述如下：

有 m 张卡片，编号从 1 到 m\xef\xbc\x8c，每张卡片都有唯一的编号。这些卡片被分发给围坐一圈的 n 个人。请注意m >= n。

然后我们选择坐在“p”位置的人“A”出圈，就像约瑟夫斯问题一样。下一步我们跳过p右边的“k”个人，而k是“A”人拿的牌的编号，我们做同样的事情，直到圈子里只剩下一个人。

问题是给定n个人和m张牌，我们是否可以选择n张牌并将它们分配给n个人，使得无论从哪个位置开始（排除第一个位置），最后生存的人始终是队伍中的第一个人圆圈。

例如，m = n = 5，唯一的解是(4,1,5,3,2)。

我认为这个问题是一个np完全问题，但我无法证明。有人有找到多项式时间解决方案或证明它是 np 困难的好主意吗？

--- 示例解决方案 ---

 2: [ 1,  2]\n 2: [ 2,  1]\n 3: [ 1,  3,  2]\n 3: [ 3,  1,  2]\n 4: [ 4,  1,  3,  2]\n 5: [ 4,  1,  5,  3,  2]\n 7: [ 5,  7,  3,  1,  6,  4,  2]\n 9: [ 2,  7,  3,  9,  1, …

我想收集 [a, b] 范围内阶乘以偶数开头的所有数字。

例如：

a = 1, b = 10

回答：

2 3 4 8

解释：

2! = 2 = starts with even
3! = 6 = starts with even
4! = 24 = starts with even
8! = 40320 = starts with even

限制条件：

1 <= a,b <= 100

这是我的代码：

List<Integer> process(int a, int b) {
    long base = i;
    for(int i=1; i<=a; i++) base *= i;
    
    if(even(base)) list.add(a);
    
    for(int i=a+1; i<=b; i++) {
        base *= i;
        if(even(base)) …