数组分组算法求最小分组

suxiaochen 2011-10-07 04:55:31
有一整数数组,无重复元素,按升序排列。先要求将元素分组,分组要求如下:

每一组中,任意两个元素差值不超过给定值。

求最先分组。


一个具体的例子:

整数数组,100个元素,大小从1~300,无重复,升序排列,要求分组后,每组中任意两个元素差小于等于5。

我的做法,分两步:

1.扫描数组,一次取出前后两个元素,如果差大于5,就在那个地方断开
第一轮是将给定数组从整体上,处理一下,处理后得到N个小数组

2.处理每个小数组(各自都是从小到打的排序),以第一个元素为标准,一直往后找,直到超出范围,至此为一组。
更新标准,继续往后找。直到结束。

虽然感觉这样做求出的是最优的解,但是还是不知道如何进行数学上的证明:

大致感觉是这样的:

[A11 ...... A1m]
[A21 ...... A2m]
................
[An1 ...... Anm]

Anm > An(m-1) > ... > An1
Anm <= An1 + delta
An1 > A(n-1)1 + delta

假设现在有N组,且不是最优的,最优的是N-1组,那么势必:两个整组合并,这样就不满足条件了(任意两个元素差值)


希望有高手能够给点意见,首先这个算法是否最优。如何证明?
...全文
328 4 打赏 收藏 转发到动态 举报
写回复
用AI写文章
4 条回复
切换为时间正序
请发表友善的回复…
发表回复
SuperFC 2011-10-08
  • 打赏
  • 举报
回复
对“最先分组”的解释应该就是1楼那样吧!
商科程序员 2011-10-08
  • 打赏
  • 举报
回复
如一楼,时间复杂度O(n),没必要像楼主那样O(2n).
LZ第一遍检查跨度大于5的一步重复了.第二步一样会把第一步的组正确分出来,并且复杂度不会提高.
chhch11111 2011-10-08
  • 打赏
  • 举报
回复
如一楼,直接贪心就可以了
keeya0416 2011-10-07
  • 打赏
  • 举报
回复
不知道是不是我理解有误
直接从头往尾取
第一个数与被取到的最后的那个数的差值在要求范围内不就够了吗

1 2 3 4 5 6 7 8 9 10 11 17 21 22 23 24
分成
1 2 3 4 5 6
7 8 9 10 11
17 21 22
23 24

33,006

社区成员

发帖
与我相关
我的任务
社区描述
数据结构与算法相关内容讨论专区
社区管理员
  • 数据结构与算法社区
加入社区
  • 近7日
  • 近30日
  • 至今
社区公告
暂无公告

试试用AI创作助手写篇文章吧