给定一个空数组,我需要进行两种类型的查询
在数组中插入元素
找到一些元素k的索引(显然数组必须保持排序)
这可以使用set容器来完成
set<int> st;
set.insert(t);
这将插入我的元素O(log(n)).
并为第二个查询
set<int>::iterator it;
it = st.find(k);
idx = distance(st.begin(), it);
这需要O(n)时间.(O(n)[为distance()[+ O(log(n)[for set::find()]).
有没有办法在O(log(n))使用预定义的C++容器时进行这两个查询？
我们需要在两个字符串之间找到最短的不常见子字符串,即如果我们有两个字符串a,b那么我们需要找到其中最短子字符串的长度a不是子字符串b.
如何使用后缀数组解决这个问题？
要求解决的复杂度不超过n*lg(n)
Mastermind是两个玩家的游戏.在开始的时候,第一个球员决定密钥,这是一个序列(s1,s2,...sk),其中0 < si <= n,然后第二个玩家使得回合,每个猜测是形式的猜测(g1,g2, ...gk),而每次猜测后第一个球员计算猜比分.猜测的分数等于我们拥有的i的数量gi = si.
例如,如果密钥是(4,2,5,3,1)并且猜测是(1,2,3,7,1),那么分数是2,因为
g2 = s2和g5 = s5.
给定一系列猜测和每个猜测的分数,您的程序必须确定是否存在至少一个生成这些精确分数的密钥.
输入
输入的第一行包含一个整数Ç (1 <=C <= 100).C测试案例如下.每个测试用例的第一行包含三个整数n,k和q.(1 <=n,k <=11, 1<=q<=8).接下来的q行包含猜测.
每个猜测由k个整数组成,gi,1, gi,2,....gi,k由单个空格分隔,然后是猜测bi的分数 (1 <= gi,j <=n for all 1 <=i <=q, 1 <=j <=k; and 0 <= bi <=k )
产量
对于每个测试用例,如果至少存在生成那些精确分数的密钥,则输出"是"(不带引号),否则输出"否".
样本输入 …
给定二叉搜索树,其中交换任意两个节点.所以我们需要找到这两个节点并将它们交换回去(我们需要交换节点,而不是交换数据)
我尝试通过创建一个具有inorder遍历树的附加数组来执行此操作,并将指针保存到每个节点.然后我们遍历数组并找到不在排序顺序中的两个节点,现在在树中搜索这两个节点然后交换
所以我的问题是如何在O(1)空间中解决这个问题？
有人可以告诉我如何检查消息队列中是否有任何消息.消息队列在基于Linux的操作系统的C中实现.我只想检查特定时间消息队列中是否有任何消息.