小编out*_*law的帖子

我需要一个像STL multiset一样工作的数据结构,但Java中的TreeSet不允许重复元素.Java中是否有内置的数据结构,相当于multiset？

我遇到了一个需要Queue数据结构支持快速第k个最大元素查找的问题.

该数据结构的要求如下:

1. 队列中的元素不一定是整数,但它们必须相互比较,即当我们比较两个元素时它们可以分辨哪一个更大(它们也可以相等).

2. 数据结构必须支持入队(在尾部添加元素)和出列(删除头部的元素).

3. 它可以快速找到队列中第k个最大的元素,请注意k不是常数.

4. 您可以假设操作入队,出列和第k个最大元素查找都以相同的频率发生.

我的想法是使用修改后的平衡二叉搜索树.该树与普通平衡二叉搜索树相同,除了每个节点_i用另一个字段n _i增强,n _i表示包含在具有根节点_i的子树中的节点的数量.上述操作支持如下:

为简单起见,假设所有元素都是不同的.

Enqueue(x):首先将x插入树中,假设相应的节点是节点_t,我们将对(x,指向节点_t的指针)附加到队列.

出队:假设(e1,节点₁)是头部的元素,节点₁是指向对应于e1的树的指针.我们从树中删除节点₁并从队列中删除(e1,节点₁).

第K个最大元素发现:假设根节点是节点_根,它的两个子节点是节点_左边和节点_右边(假设它们都存在),我们将K与n _根比较,可能发生三种情况:

1. 如果满足K <N _左我们发现在n的左子树的第K个最大元素_根 ;

2. 如果K> n _root -n _right,我们在n _root的右子树中找到(Kn _root + n _right)第n 个最大元素;

3. 否则n _root是我们想要的节点.

所有三个操作的时间复杂度为O(log _N),其中N是当前队列中的元素数.

如何加快上述操作？什么数据结构和如何？

给定[0,10000]之间的n个整数作为D ₁,D ₂ ...,D _n,其中可能存在重复,并且n可以是巨大的:

我想在[0,10000]之间找到k个不同的代表性整数(例如k = 5)作为R ₁,R ₂,...,R _k,因此所有代表性整数的误差之和被最小化.

代表性整数的错误定义如下:

假设我们将k个代表整数按升序排列为{R ₁,R ₂ ...,R _k },则R _i的误差 为:

我想最小化k代表整数的错误总和:

怎么能有效地完成？

EDIT1: k代表整数中最小的一个必须是{D ₁,D ₂ ...,D _n }中的最小数字

EDIT2: k代表整数中最大的一个必须是{D ₁,D ₂ ...,D _n }中的最大数字加1.例如,当{D ₁,D ₂ ...,D _n中的最大数字时是9787然后R _k是9788.

EDIT3:这里有一个具体的例子:

D = {1,3,3,7,8,14,14,14,30},如果k = 5且R被选为{1,6,10,17,31},那么误差之和为:

误差总和=(1-1)+(3-1)*2 +(7-6)+(8-6)+(14-10)*3 +(30-17)= 32

这是因为1 <= 1,3,3 <6,6 <= 7,8 <10,10 <= 14,14,14 <17,17 <= 30 <31

假设我们有一组n个不相交的节点{节点₁,节点₁,...,节点_n }

以下3个操作的最快数据结构和算法是什么:

1. Union(x,y):在节点_x和节点_y之间添加无方向边,两个节点之间最多可以有一条边.

2. IsConnected(x,y):如果节点_x和节点_y直接或间接连接,则返回true ,即节点_x和节点_y在同一个连接组件中.

3. Un-union(x,y):删除节点_x和节点_y之间的边(如果存在).

Disjoint-set是前两个操作的完美数据结构,但它不能直接支持第3个操作.有什么选择？

如果我们模拟过程,第一个和第三个操作可以在O(1)中实现,但第二个操作是O(n),所以我想看看是否可以在O(logn)时间内运行所有三个操作或更少.

假设我们有一个连通和无向图:G =(V,E).

连通集的定义:属于G的V的一组点形成有效的连通集如果该组中的每个点都在距离同一组中的任何其他点的T-1个边缘内,则T是所述点中的点数.群组.

请注意,连接集只是G的连接子图,没有边但是带有点.

并且我们在连接集上定义了任意函数​​F,即给定任意连接集CS F(CS)将给出一个实数值.

如果它们的并集不是连接集,则说两个连接集是不相交的.

有关视觉说明,请参见下图:在图表中,红色,黑色,绿色点集都是有效的连接集,绿色集与红色集不相交,但黑色集与红色集不相交.

现在的问题是:我们希望从G中找到一堆不相交的连接集,以便:(1)每个连接集至少有K个点.(K是全局参数).(2)它们的函数值之和,即max(ΣF(CS))被最大化.

除了详尽的搜索之外,是否有任何有效的算法来解决这样的问题？谢谢!

例如,图形可以是2D欧几里得平面中的平面图形,并且连通集合CS的函数值F可以定义为CS中所有点的最小边界矩形的面积(最小边界矩形是包含CS中所有点的最小矩形.

给定2D欧几里得平面中的一组点:P = {V ₁,V ₂,...,V _n },并且我们假设存在K种不同类型的点:T ₁,T ₂,...,T _K,P中的每个点V _i都属于K类型中的一个.

游解KTSP的定义:
给定一个任意位置点V ₀中相同的2D平面欧几里得(V ₀没有类型),一个路V ₀ > - V ^' ₁ > - V ^' ₂ > - V ^' ₃ - > ... .-> V ^' _ķ > - V ₀被称为游解KTSP当且仅当V ^' _我属于I型.

KTSP巡回赛只是一个普通的巡回赛,以同一个给定的任意点开始和结束,但还有两个限制:(1)它通过每种类型的第一个点,只传递一次.(2)路径经过的点的类型有顺序.也就是说,它首先从点V ₀开始,然后首先通过类型T1点,然后键入T2点,然后键入T3点,依此类推,直到它通过类型T _K点,之后它返回到V ₀.

这是我的问题:
当给出点位置V ₀时,找到最短的KTSP巡回赛.

例如,在下图中,每种颜色代表一种类型的点,有3种不同类型的点,我们假设蓝色点是类型1,红色类型2,黑色类型3,
带有黄色的小三角形是给定的在位置V ₀,然后用四个蓝色箭头示出对应于该特定V ₀的最短TSKP巡回.

在我看来这是经典TSP问题的一个变种,但我想不出一个算法,需要帮助!