两个递增数列合并排序（两个数列中相同的数只保留一个），求第n个数（再讨论）

止戈而立 2009-02-23 11:06:56
上一个帖被我结掉了，
http://topic.csdn.net/u/20090220/13/7f6df674-dbda-4842-b51a-8f9fcfec7a2b.html
结得有些早了，觉得这个还可以再进一步地讨论，请大家在这个帖子留个名，然后到原来帖子上进行讨论：

已知数A和数B：
存在两数列：
数列一：(A-B)、3(A-B)、5(A-B)、7(A-B)、9(A-B)、……
数列二：(A+B)、3(A+B)、5(A+B)、7(A+B)、9(A+B)、……

求两个数列合并后，第n个数。

(A+B)和(A-B)的最小公倍数将是共同的数，那么n倍最小公倍数也将是两个数列共同的数。
...全文
991 36 打赏 收藏 转发到动态 举报
写回复
用AI写文章
36 条回复
切换为时间正序
请发表友善的回复…
发表回复
ask8cn 2011-06-05
  • 打赏
  • 举报
 回复
为什么不用递归？
owenliangbin 2009-02-25
  • 打赏
  • 举报
 回复
刚刚测试了下n=1e,用了1s
owenliangbin 2009-02-25
  • 打赏
  • 举报
 回复
改改，原理一样，测试了一下，有点小毛病。
long n_value=(n*2-1)*(A-B);
for(int i=1;i <=2*n;i+=2)
{

if(i*(A+B)>n_value)return n_value/(A-B)/(A+B);
if(i*(A+B)>n_value-2*(A-B))return i/(A-B);
n_value-=2*(A-B);
}
owenliangbin 2009-02-25
  • 打赏
  • 举报
 回复
我这个绝对快而短。
晕，不是指我个人。
long n_value=n*(A-B);
for(int i=1;i <=n;i++)
{

if(i*(A+B)>n_value)return n_value/(A-B)/(A+B);
if(i*(A+B)>n_value-2*(A-B))return i/(A-B);
n_value-=2*(A-B);
}
linux_wxst 2009-02-25
  • 打赏
  • 举报
 回复
我用二分法写了一个程序，时间复杂度是log(N)。楼主可以测试一下。

int common_multi(int m, int n)
{
int k = m * n;
int tmp = m % n;

while (tmp != 0) {
m = n;
n = tmp;
tmp = m % n;
}

return k / n;
}

int main()
{
int A, B, N;
int a, b, c, sum, left, right, mid;
int tmp1, tmp2, flag;

scanf("%d%d%d", &A, &B, &N);
a = A - B;
b = A + B;
c = common_multi(a, b);
left = A - B;
right = (2 * N - 1) * (A + B);

if ((c/a) % 2 == 0 || (c/b) % 2 == 0) {
flag = 1;
} else {
flag = 0;
}


while (left <= right ) {
mid = (left + right) / 2;
sum = (mid/a + 1) / 2 + (mid/b + 1) / 2;
if (flag == 0) {
sum -= mid / c;
}
if (sum == N) {
break;
} else if (sum < N) {
left = mid + 1;
} else {
right = mid - 1;
}
}

tmp1 = mid / a;
tmp2 = mid / b;
if (tmp1 % 2 == 0) {
tmp1 --;
}
if (tmp2 % 2 == 0) {
tmp2 --;
}
tmp1 *= a;
tmp2 *= b;
if (tmp1 > tmp2) {
printf("%d / %d\n", tmp1, a * b);
} else {
printf("%d / %d\n", tmp2, a * b);
}

return 0;
}
绿色夹克衫 2009-02-24
  • 打赏
  • 举报
 回复
这里还应该有个9吧?不知道是不是这个原因造成的测试错误!

[Quote=引用 13 楼 min_jie 的回复:]
A=4,B=1时的输出(放大(A+B)(A-B)倍)：
3 5 15 15 21 25 27 33 39 45 45 51 55 57 65 69 75 75 81 85
[/Quote]
lzonline01 2009-02-24
  • 打赏
  • 举报
 回复
给分吗?
dhb008 2009-02-24
  • 打赏
  • 举报
 回复 
//精彩！！！！！
绿色夹克衫 2009-02-24
  • 打赏
  • 举报
 回复
原来这个程序还可以用来算这个,真没想到呀!

其实我的算法理论也挺差的,否则也不会错这么多次,不过学习算法本身挺有乐趣的,要比做项目有趣多了.

和LZ共同学习.

[Quote=引用 29 楼 min_jie 的回复:]
引用 28 楼 litaoye 的回复:
呵呵,还是多测试一些吧!搞不清还有什么其他问题没有!写了这么多个错的,才折腾出来,真不好意思!

其实思路上一直都没有变!不过转成程序被我弄复杂了!后面的方法简洁了一些,错误也就排除了一些.

我的算法理论真的很糟，还请多多指教！

这个问题是我上次看了一个两车对开相遇的帖子后，引申出来的。自己想得头脑发乱。。
拿这个排序后的数列除以(A+B)(A-B)就是相遇的时间。原数列一…
[/Quote]
止戈而立 2009-02-24
  • 打赏
  • 举报
 回复
[Quote=引用 28 楼 litaoye 的回复:]
呵呵,还是多测试一些吧!搞不清还有什么其他问题没有!写了这么多个错的,才折腾出来,真不好意思!

其实思路上一直都没有变!不过转成程序被我弄复杂了!后面的方法简洁了一些,错误也就排除了一些.


[/Quote]

我的算法理论真的很糟，还请多多指教！

这个问题是我上次看了一个两车对开相遇的帖子后，引申出来的。自己想得头脑发乱。。
拿这个排序后的数列除以(A+B)(A-B)就是相遇的时间。原数列一是异向相遇，原数列二是同向相遇。。
绿色夹克衫 2009-02-24
  • 打赏
  • 举报
 回复
呵呵,还是多测试一些吧!搞不清还有什么其他问题没有!写了这么多个错的,才折腾出来,真不好意思!

其实思路上一直都没有变!不过转成程序被我弄复杂了!后面的方法简洁了一些,错误也就排除了一些.

[Quote=引用 27 楼 min_jie 的回复:]
引用 25 楼 litaoye 的回复:
都不好意思全贴了,搞定了后面的,前面又出了问题,呵呵!

改了之后,存在remain == 2的情况了,所以要多一个判断了!
[/Quote]
止戈而立 2009-02-24
  • 打赏
  • 举报
 回复
[Quote=引用 25 楼 litaoye 的回复:]
都不好意思全贴了,搞定了后面的,前面又出了问题,呵呵!

改了之后,存在remain == 2的情况了,所以要多一个判断了!

[/Quote]


ls3697264 2009-02-24
  • 打赏
  • 举报
 回复
UP
绿色夹克衫 2009-02-24
  • 打赏
  • 举报
 回复
都不好意思全贴了,搞定了后面的,前面又出了问题,呵呵!

改了之后,存在remain == 2的情况了,所以要多一个判断了!



            //找出少的那个数

            if (remain > 0)

                FirstA = Math.Min(FirstA + increaseA, FirstB + increaseB);



======>



            //找出少的那个数

            if (remain == 1)

                FirstA = Math.Min(FirstA + increaseA, FirstB + increaseB);

            else if (remain == 2)

                FirstA = Math.Max(FirstA + increaseA, FirstB + increaseB);
止戈而立 2009-02-24
  • 打赏
  • 举报
 回复
确实难搞，A=9,B=1有问题
zgke 2009-02-24
  • 打赏
  • 举报
 回复
留个脚印
绿色夹克衫 2009-02-24
  • 打赏
  • 举报
 回复
又改了1个出来,呵呵,真是错误百出呀(其实从头到尾都是取整问题,有时候上取整,有时候下取整),不知道这次对了没有!



        static double getItem(long A, long B, long N)

        {

            //计算初始值

            long startA = A - B;

            long startB = A + B;



            //计算递增

            long increaseA = startA << 1;

            long increaseB = startB << 1;



            //求最大公约数,计算循环节长度

            long maxcd = maxCommonDivisor(increaseA, increaseB);

            long looplength = increaseA / maxcd + increaseB / maxcd;



            //计算第一个循环的位置

            long firstLoop = looplength >> 1;



            //如果循环节长度为奇数,则不会重复

            if ((looplength & 1) == 0 && N > firstLoop)

            {

                //根据循环节长度推算本来的N值(不删除元素的情况下)

                long increase = (N - firstLoop) / (looplength - 1) + 1;

                N += increase;

            }





            //计算对应A数组的位置和B数组的位置,及对应的值

            long IndexA = (N * startB / A) >> 1;

            long FirstA = IndexA * increaseA - startA;

            long IndexB = (FirstA + startB) / increaseB;

            long FirstB = IndexB * increaseB - startB;



            //由于取整的缘故,可能会少1个数

            long remain = N - IndexA - IndexB;



            //找出少的那个数

            if (remain > 0)

                FirstA = Math.Min(FirstA + increaseA, FirstB + increaseB);



            double result = (double)FirstA ;// (double)(startA * startB);

            return result;

        }
Cherishny 2009-02-24
  • 打赏
  • 举报
 回复
A > B
y = (A-B)*(2x-1)
y = (A+B)*(2x-1)
这两个函数的
Y相同时 x值的比较
绿色夹克衫 2009-02-24
  • 打赏
  • 举报
 回复
上面给的程序确实有问题,自测了一下,除了循环节算对了,剩下的问题还挺多,

修改了一下,测了A=4,B=1的情况,没发现什么问题,不知道还会哪里出错。

这道题测试起来确实有些麻烦，还得专门写个程序测试。



        static double getItem(long A, long B, long N)

        {

            //计算初始值

            long startA = A - B;

            long startB = A + B;



            //计算递增

            long increaseA = startA << 1;

            long increaseB = startB << 1;



            //求最大公约数,计算循环节长度

            long maxcd = maxCommonDivisor(increaseA, increaseB);

            long looplength = increaseA / maxcd + increaseB / maxcd;



            //如果循环节长度为奇数,则不会重复

            if ((looplength & 1) == 0)

            {

                //根据循环节长度推算本来的N值

                long firstLoop = looplength >> 1;



                if (N > firstLoop)

                {

                    long increase = (N - firstLoop) / (looplength - 1) + 1;

                    N += increase;

                }

            }



            long IndexA = (N * startB / A) >> 1;

            long IndexB = (N * startA / A) >> 1;



            long FirstA = IndexA * increaseA - startA;

            long FirstB = IndexB * increaseB - startB;



            long remain = N - IndexA - IndexB;



            if (remain > 0)

                FirstA = Math.Min(FirstA + increaseA, FirstB + increaseB);



            double result = (double)FirstA / (double)(startA * startB);

            return result;

        }
Cherishny 2009-02-24
  • 打赏
  • 举报
 回复
应该是两路归并算法
加载更多回复（16）
PHP实现合并两个排序链表的方法
由于两个数列本来就是递增的，所以每次将两个数列中较小的部分拿过来就可以了。 实现代码 <?php /*class ListNode{ var $val; var $next = NULL; function __construct($x){ $this->val = $x; } }*/ ...
判断链表是否为回文链表leetcode-Algorithms:Coding_Interviews和Leetcode
合并两个递增排序的链表 连续子序列的最大和 替换空格 二维数组中的查找 从尾到头打印链表 重建二叉树(用前序和中序构建) 从上到下打印二叉树（层序遍历） 用两个栈实现队列 斐波那契数列 旋转数组的最小数字 矩阵中...
高级互联网架构：百度UidGenerator分布式组件
在大型分布式系统中，经常有生成全局唯一ID标识的需求，比如 支付、订单、红包、优惠券、跟踪号等等，那么关于如何优雅地生成一个分布式全局唯一ID标识，大家是否思考过如下问题： 1.全局唯一，不能重复，这是基本...
Description 有两个有序数列，数据个数分别为m和n，每个数列中的数均从小到大有序排列。 请把这两个数列合并为一个，输出合并后的数列。 Input 输入数据有两组，每组数据分两行，第1行为两个
/*Description 有两个有序数列，数据个数分别为m和n，每个数列中的数均从小到大有序排列。 请把这两个数列合并为一个，输出合并后的数列。...输入保证两个数列中的数任意两个都不相等。 Output 对于每组...
013.【排序算法】合并排序法
合并排序法是针对已经排序好的两个或两个以上的数列，通过合并的方式，将其组合成一个大的且排序好的数列。首先是将无序的数列分成若干小份，分若干份的规则就是不断把每段长度除以2（对半分），直到分到不能再分为...
C#

110,539

社区成员

642,577

社区内容

发帖
与我相关
我的任务
社区描述
.NET技术 C#
社区管理员
  • C#
  • Web++
  • by_封爱
加入社区
  • 近7日
  • 近30日
  • 至今

加载中

查看更多榜单
社区公告

让您成为最强悍的C#开发者

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

+ 用AI写文章