【一个算法题】一起来写一把。解决办法

2013-01-26

【一个算法题】一起来写一把。题目：You are given an array or integers.Please write a method to return al

【一个算法题】一起来写一把。
题目：
You are given an array or integers. Please write a method to return all unique pairs of integers which sum up to 5. For example:

If you are given this array: [1,-3,9,4,2,5,1,-4,0], your method should return {[1,4], [9,-4], [5,0]}.

我写了一种O(NLogN)的方式：(但我觉得肯定还有优化的余地，maybe可以达到O(N))


static void Main(string[] args)
        {
            int[] arr = new int[] { 1, -3, 9, 4, 2, 5, 1, -4, 0 };
            print(arr);
        }
 
        private static void print(params int[] integers)
        {
            bubbleSort(integers);
            find(integers, 0, integers.Length - 1);
        }
 
        private static void find(int[] integers, int begin, int end)
        {
            int sum = 5;
            for (int i = begin; i < end; i++)
            {
                int v = integers[i];
                int j = end;//integers.Length - 1;
                int b = integers[j];
 
                if (i > 0 && v == integers[i - 1])
                    continue;
 
                if (v + b < sum)
                    continue;
                else if (v + b == sum)
                {
                    ok(v, b);
 
                    if (j - 1 <= i + 1)
                        continue;
 
                    find(integers, i + 1, j - 1); 
 
                }
                else //v + b < sum
                {
                    if (j - 2 <= i + 1)
                        continue;
 
                    find(integers, i + 1, (j--) - 1);
                }
 
                i = j;
            }
        }
 
        static void bubbleSort(params int[] arr)
        {
            for (int j = 1; j < arr.Length; j++)
            {
                for (int i = 0; i < arr.Length - j; i++)
                {
                    if (arr[i] > arr[i + 1])
                    {
                        int temp = arr[i];
                        arr[i] = arr[i + 1];
                        arr[i + 1] = temp;
                    }
                }
            }
        }
 
        private static void ok(int a, int b)
        {
            Console.WriteLine(a + "," + b);
        }

[解决办法]
看看走走逛逛！
[解决办法]
【一个算法题】一起来写一把。解决办法

看见了冒泡还O（LogN）呢
[解决办法]
O（NLogN）
------解决方案--------------------

【一个算法题】一起来写一把。解决办法参考快速排序(return all unique pairs of integers which sum up to 5这种按照快排思想改改就行了)
[解决办法]
好吧可以是O（NLogN）（排序算法时间复杂度为O（N LogN）前提下）
[解决办法]

[解决办法]
直接顺序取值i
然后计算
x1=5-i
x2=i-5
查找这x2,x2两个值是否在集合内，如果在就得到匹配的对，然后移除匹配项。重复上述过程就是

ps：如果不是啥考试题目，俺都会直接使用linq的group分组了，分组标准就是上面那两个东西
[解决办法]
首先我没觉得，你那个排序有用，如果不排序，你那个遍历得不到结果吗
即使你非得用排序，对于小数组也就算了，对于大数组，冒泡排序效率太低，改用快排或其他
[解决办法]


我觉得优化的地方在于：
因为 SUM = 5，所以对于正数而言，pair 的组合方式无非这几种：[0,5], [1,4], [2,3]
在你自定义的 bubble sort 的过程中设置一个长度为 6 的 flag 数组：bool[] flags = new bool[6];
每一个布尔值对应 0,1,2,3,4,5 是否存在。
在排序之后，首先检查这个 flag 数组，如果 flags[0] 和 flags[5] 存在，则存在 [0,5] 这个 pair
因为根据提议，结果是去重复的，所以对于正数的情况这个即可了。
在这个循环标记判断的过程中，可以直接把 0,1,2,3,4,5 这 6 个数字删掉，你可以想想是不是？
因为排序是必须的，所以，我们必须利用排序，在里面做事情。
再来看负数的情况，负数的情况就直接按照算法，因为已经排序了，所以基本按照你原先的算法，我觉得就可以了
但是有一点可以小优化：当某一个负数遇到一个与之 SUM 之后，value 不大于 5 的情况，
那么这个负数不在考虑。换下一个，对吧？这个时候你可以把这个正数 X 记下来，算出要得到 5，需要的负数是几，然后从头部进行循环比较，比到类似的情况，跳出，然后继续比较右侧正数。等会我来举个例子

[解决办法]
我的比较算法是这样的：


假设经过排序，有以下数组：
-40, -38, -30, -20, -15, -14, -12, -1, 0, 1, 2, 3, 4, 5, 6, 18, 22, 30, 36, 38, 42, 70
然后在排序之后去掉 0 ~ 5，之后变成：
-40, -38, -30, -20, -15, -14, -12, -1, 6, 18, 22, 30, 36, 38, 42, 70
这个时候设头尾两个变量 i, j 分别指向第一个和最后一个，然后：
(1) 从第一个开始，-40 需要配对 45，从 70 开始找，到了 42，发现已经小了，就停止，然后 i 指向 -38
(2) 从 42 开始，42 需要 -37，-38 小于 -37，继续，然后碰到 -30，-30大于-37，跳出，然后 j 指向 38
(3) 接着交替从左侧 -30 开始，它需要 35 才能配对，所以右侧 j 一直循环到 30，跳出，因为已经小了。
     ......
就这样，一直左右交替，避免递归，因为你这个毕竟不是尾递归。编译器不能对其堆栈数据进行优化。
这个和你的是不是有点相似？我大致看了你的算法，没有仔细看，但是感觉到你用到递归，所以不是很理想。

[解决办法]
哦，是吗？那老赵扯的这些没用喽？反正 C# 会与优化，要化解为尾递归干什么？
http://www.cnblogs.com/JeffreyZhao/archive/2009/04/01/1424028.html
[解决办法]


class Program
    {
        static void Main(string[] args)
        {
            int[] arr = new int[] { 1, -3, 9, 4, 2, 5, 1, -4, 0 }; 
 

            Dictionary<int, int> result = GetUniqueResult(arr);

            foreach (var item in result)
            {
                Console.WriteLine("{0} {1}", item.Key, item.Value);
            }

            Console.Read();
        }

        static Dictionary<int, int> GetUniqueResult(int[] arr)
        {
            Dictionary<int, int> dic = new Dictionary<int, int>();

            Dictionary<int, int> result = new Dictionary<int, int>();

            for (int i = 0; i < arr.Length; i++)
            {
                if (!dic.ContainsKey(5 - arr[i]))
                {
                    dic[5 - arr[i]] = arr[i];

                    if (dic.ContainsKey(arr[i]))
                    {
                        result[arr[i]] = dic[arr[i]];
                    }
                }
            }

            return result;
        }
    }

[解决办法]
楼上的方法挺好，受你启发，用 Lambda 玩玩：


int[] arr = new int[] { 1, -3, 9, 4, 2, 5, 1, -4, 0 };
var ts = arr.Select(i => new Tuple<int, int>(5 - i, i)).Distinct()
            .Where (t => arr.Contains(t.Item1))
            .Select(t => (t.Item1 <= t.Item2) ? t : new Tuple<int, int>(t.Item2, t.Item1)).Distinct();
foreach (var t in ts)
{
    Console.WriteLine("{0} {1}", t.Item1, t.Item2);
}

[解决办法]
的确是吐槽，因为俺们不矫情

俺们矫情他作甚，又不是写论文。就算俺你的排序。俺们也直接Array.sort,把后面的比较接口重新实现一下就是
这玩意知道就ok，快排让你手写你会就ok，俺们这里不像博客园，喜欢矫情。俺们这里讲实用，不讲矫情
[解决办法]

引用:

题目：
You are given an array or integers. Please write a method to return all unique pairs of integers which sum up to 5. For example:

If you are given this array: [1,-3,9,4,2,5,1,-4,……

有bug

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static?void?Main(string[]?args)
????????{
            Random rnd = new Random();
            int[] arr = Enumerable.Range(0, 100).Select(x => rnd.Next(-10, 10)).ToArray();
????????????print(arr);
????????}
??
????????private?static?void?print(params?int[]?integers)
????????{
????????????bubbleSort(integers);
????????????find(integers,?0,?integers.Length?-?1);
????????}
??
????????private?static?void?find(int[]?integers,?int?begin,?int?end)
????????{
????????????int?sum?=?5;
????????????for?(int?i?=?begin;?i?<?end;?i++)
????????????{
????????????????int?v?=?integers[i];
????????????????int?j?=?end;//integers.Length?-?1;
????????????????int?b?=?integers[j];
??
????????????????if?(i?>?0?&&?v?==?integers[i?-?1])
????????????????????continue;
??
????????????????if?(v?+?b?<?sum)
????????????????????continue;
????????????????else?if?(v?+?b?==?sum)
????????????????{
????????????????????ok(v,?b);
??
????????????????????if?(j?-?1?<=?i?+?1)
????????????????????????continue;
??
????????????????????find(integers,?i?+?1,?j?-?1);
????????????????}
????????????????else?//v?+?b?<?sum
????????????????{
????????????????????if?(j?-?2?<=?i?+?1)
????????????????????????continue;
??
????????????????????find(integers,?i?+?1,?(j--)?-?1);
????????????????}
??
????????????????i?=?j;
????????????}
????????}
??
????????static?void?bubbleSort(params?int[]?arr)
????????{
????????????for?(int?j?=?1;?j?<?arr.Length;?j++)
????????????{
????????????????for?(int?i?=?0;?i?<?arr.Length?-?j;?i++)
????????????????{
????????????????????if?(arr[i]?>?arr[i?+?1])
????????????????????{
????????????????????????int?temp?=?arr[i];
????????????????????????arr[i]?=?arr[i?+?1];
????????????????????????arr[i?+?1]?=?temp;
????????????????????}
????????????????}
????????????}
????????}
??
????????private?static?void?ok(int?a,?int?b)
????????{
????????????Console.WriteLine(a?+?","?+?b);
????????}

    }
}

总是输出 -4, 9
[解决办法]
不知道
[1,-3,7]
算不

[解决办法]
unique pairs

引用:

不知道
[1,-3,7]
算不

------解决方案--------------------

我看了一下你的算法，总感觉不对哦。
[解决办法]
假设Hashtable的存取可以到达O(N)，那么下列的算法的计算复杂度为O(N)。
其中：
Dictionary<int, int>用来快速匹配。
HashSet<int>是为了得到不重复的对子。


static void Main(string[] args)
{
    const int SUM = 5;
    int[] arr = new int[] { 1, -3, 9, 4, 2, 5, 1, -4, 0 };

    Dictionary<int, int> pool = new Dictionary<int, int>();
    HashSet<int> results = new HashSet<int>();

    foreach (int i in arr)
    {
        if (pool.ContainsKey(i)) pool[i]++;
        else pool[i] = 1;
    }
    foreach (int i in arr)
    {
        if (pool.ContainsKey(i) && pool.ContainsKey(SUM - i))
        {
            if (--pool[i] == 0) pool.Remove(i);
            if (--pool[SUM - i] == 0) pool.Remove(SUM - i);
            results.Add(Math.Min(i, SUM - i));
        }
    }
    foreach (int i in results)
    {
        Console.WriteLine("({0},{1})", i, SUM - i);
    }
}

[解决办法]

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            Random rnd = new Random();
            int[] arr = Enumerable.Range(0, 10000000).Select(x => rnd.Next(-20, 20)).ToArray();
            DateTime dt1 = DateTime.Now;
            Console.WriteLine("starttime: {0}", dt1);
            SortedSet<int> ss = new SortedSet<int>();
            SortedSet<int> sl = new SortedSet<int>();
            for (int i = 0; i < arr.GetLength(0); i++)
            {
                int x = arr[i];
                if (x > 2) sl.Add(5 - x); else ss.Add(x); 
 
            }
            IEnumerator<int> itl = sl.GetEnumerator();
            itl.MoveNext();
            foreach (int i in ss)
            { 
                while (itl.Current < i)
                    if (!(itl.MoveNext())) goto l_end;
                if (itl.Current == i) Console.WriteLine(i + ", " + (5 - i));
            }
        l_end:
            DateTime dt2 = DateTime.Now;
        Console.WriteLine("endtime: {0}, totaltime: {1}.", dt2, new TimeSpan(dt2.Ticks - dt1.Ticks).ToString());
        }
    }
}

starttime: 2012-12-3 16:26:37
-14, 19
-13, 18
-12, 17
-11, 16
-10, 15
-9, 14
-8, 13
-7, 12
-6, 11
-5, 10
-4, 9
-3, 8
-2, 7
-1, 6
0, 5
1, 4
2, 3
endtime: 2012-12-3 16:26:38, totaltime: 00:00:01.5468750.
Press any key to continue . . .

1000万个数据，在Celeron D 2.4G CPU上耗时1.5秒，有比我快的么？
[解决办法]
starttime: 2012-12-3 16:28:22
-4, 9
0, 5
1, 4
endtime: 2012-12-3 16:28:22, totaltime: 00:00:00.0312500.
Press any key to continue . . .

这是例子数据和耗时。
[解决办法]

引用:

假设Hashtable的存取可以到达O(N)，那么下列的算法的计算复杂度为O(N)。
其中：
Dictionary<int, int>用来快速匹配。
HashSet<int>是为了得到不重复的对子。
C# code??123456789101112131415161718192021222324252627static void Main(string[] arg……

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            const int SUM = 5;
            Random rnd = new Random();
            int[] arr = Enumerable.Range(0, 10000000).Select(x => rnd.Next(-20, 20)).ToArray();
            DateTime dt1 = DateTime.Now;
            Console.WriteLine("starttime: {0}", dt1); 
 
            Dictionary<int, int> pool = new Dictionary<int, int>();
            HashSet<int> results = new HashSet<int>();

            foreach (int i in arr)
            {
                if (pool.ContainsKey(i)) pool[i]++;
                else pool[i] = 1;
            }
            foreach (int i in arr)
            {
                if (pool.ContainsKey(i) && pool.ContainsKey(SUM - i))
                {
                    if (--pool[i] == 0) pool.Remove(i);
                    if (--pool[SUM - i] == 0) pool.Remove(SUM - i);
                    results.Add(Math.Min(i, SUM - i));
                }
            }
            foreach (int i in results)
            {
                Console.WriteLine("({0},{1})", i, SUM - i);
            }
            DateTime dt2 = DateTime.Now;
            Console.WriteLine("endtime: {0}, totaltime: {1}.", dt2, new TimeSpan(dt2.Ticks - dt1.Ticks).ToString());
        }
    }

}

starttime: 2012-12-3 16:31:33
(-13,18)
(1,4)
(-11,16)
(2,3)
(-4,9)
(-3,8)
(-10,15)
(-6,11)
(0,5)
(-2,7)
(-7,12)
(-5,10)
(-12,17)
(-1,6)
(-8,13)
(-14,19)
(-9,14)
endtime: 2012-12-3 16:31:38, totaltime: 00:00:04.7812500.
Press any key to continue . . .

同学你输啦。
[解决办法]
else //v + b < sum
{
if (j - 2 <= i + 1)
continue;

find(integers, i + 1, (j--) - 1);
}
这里的find函数参数(i+1) 感觉用 i就可以了。
[解决办法]
有人说LINQ效率低，嘿嘿，低么？

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            Random rnd = new Random();
            int[] arr = Enumerable.Range(0, 10000000).Select(x => rnd.Next(-20, 20)).ToArray();
            DateTime dt1 = DateTime.Now;
            Console.WriteLine("starttime: {0}", dt1);
            var arr1 = arr.Distinct().ToArray();
            var query = arr1.Where(x => x <= 2).Join(arr1.Where(x => x > 2), x => x, x => 5 - x, (x, y) => new { x, y });
            foreach (var item in query)
            {
                Console.WriteLine("({0}, {1})", item.x, item.y);
            }
            DateTime dt2 = DateTime.Now;
            Console.WriteLine("endtime: {0}, totaltime: {1}.", dt2, new TimeSpan(dt2.Ticks - dt1.Ticks).ToString());
        }
    }
}

starttime: 2012-12-3 16:42:34
(-10, 15)
(2, 3)
(-11, 16)
(-6, 11)
(-4, 9)
(-8, 13)
(-2, 7)
(0, 5)
(-13, 18)
(-1, 6)
(-14, 19)
(-12, 17)
(-7, 12)
(-5, 10)
(-9, 14)
(1, 4)
(-3, 8)
endtime: 2012-12-3 16:42:35, totaltime: 00:00:00.9843750.
Press any key to continue . . .

比我之前的还快50%+

谁超过linq的，说一声。
[解决办法]

引用:

C# code??1234567891011121314151617181920212223242526272829303132333435363738class Program { static void Main(string[] args) { int[] arr = new int[] { 1, -3, 9,……

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        { 
 
            Random rnd = new Random();
            int[] arr = Enumerable.Range(0, 10000000).Select(x => rnd.Next(-20, 20)).ToArray();
            DateTime dt1 = DateTime.Now;
            Console.WriteLine("starttime: {0}", dt1);
            Dictionary<int, int> result = GetUniqueResult(arr);
            foreach (var item in result)
            {
                Console.WriteLine("{0} {1}", item.Key, item.Value);
            }
             DateTime dt2 = DateTime.Now;
            Console.WriteLine("endtime: {0}, totaltime: {1}.", dt2, new TimeSpan(dt2.Ticks - dt1.Ticks).ToString());
        }

        static Dictionary<int, int> GetUniqueResult(int[] arr)
        {
            Dictionary<int, int> dic = new Dictionary<int, int>();

            Dictionary<int, int> result = new Dictionary<int, int>();

            for (int i = 0; i < arr.Length; i++)
            {
                if (!dic.ContainsKey(5 - arr[i]))
                {
                    dic[5 - arr[i]] = arr[i];

                    if (dic.ContainsKey(arr[i]))
                    {
                        result[arr[i]] = dic[arr[i]];
                    }
                }
            }
            return result;
        }
    }
}

starttime: 2012-12-3 16:45:55
8 -3
13 -8
-5 10
11 -6
9 -4
-14 19
6 -1
18 -13
-9 14
3 2
-10 15
7 -2
16 -11
4 1

17 -12
0 5
-7 12
endtime: 2012-12-3 16:45:56, totaltime: 00:00:00.6406250.
Press any key to continue . . .

找到一个比linq略快的。
[解决办法]

谁用汇编搞下
[解决办法]
膜拜~
[解决办法]
应该不需要排序吧
笨笨的方法算一次
1,-3,9,4,2,5,1,-4,0
1 加 -3, 循环加到 0
然后 -3 加 9 循环加到 0
以此类推，最后是 -4 + 0
循环次数n(n-1)

[解决办法]
看到各位大神的表演。。。
我只能表示真牛。。。。。。。佩服无比，要找本算法书看看了

吐个槽，我这帖子沉了，可问题还没解决，哪位高人能来帮我看看么
http://bbs.csdn.net/topics/390291769
[解决办法]

引用:

C# code??123456789101112131415161718192021222324252627282930313233343536using System;using System.Collections.Generic;using System.Linq;using System.Text; namespace ConsoleApplication1{ ……

借你的代码小改了下：

            Random rnd = new Random();
            int[] arr = Enumerable.Range(0, 10000000).Select(x => rnd.Next(-20, 20)).Distinct().ToArray();
            DateTime dt1 = DateTime.Now;
            Console.WriteLine("starttime: {0}", dt1);
            Dictionary<int, int> tmp = new Dictionary<int, int>(65537);
            int j;
            foreach (int i in arr)
            {
                if (tmp.TryGetValue(i, out j))
                {
                    Console.WriteLine(i + ", " + j);
                    tmp.Remove(i);
                }
                else
                {
                    tmp.Add(5 - i, i); 
 
                }
            }
            DateTime dt2 = DateTime.Now;
            Console.WriteLine("endtime: {0}, totaltime: {1}.", dt2, new TimeSpan(dt2.Ticks - dt1.Ticks).ToString());
            Console.Read();

starttime: 2012-12-03 17:30:06
6, -1
8, -3
16, -11
-13, 18
10, -5
-14, 19
5, 0
13, -8
4, 1
9, -4
-7, 12
-6, 11
7, -2
3, 2
14, -9
-10, 15
17, -12
endtime: 2012-12-03 17:30:06, totaltime: 00:00:00.0730042.

为什么那么快？其实很简单，虽然你这里有10000000个随机数，但是输出要做到无重复的话，每个数只能唯一参与一次，你后面用HashSet进行去重复工作，那我还不如一开始就用Distcint()去了重复后处理。因此你的测试结果是有误的，完全无法作为参考。另外你不用break而选择Goto跳出循环，十分的不规范，C#又不是没办法跳出循环了。
[解决办法]

引用:

引用:C# code??123456789101112131415161718192021222324252627282930313233343536using System;using System.Collections.Generic;using System.Linq;using System.Text; namespace Co……

为什么用goto？因为是两重循环，跳出多重循环，我就喜欢用goto，写着方便，看着舒服。
为什么你的快那么多？因为我的CPU是31级流水线，2004年面市的，只有256K二级缓存的可怜巴巴的Celeron D 2.4GHz。在很多基准测试中，Core i7 3.4GHz单线程运算能力竟然能达到我的CPU的8~10倍！
[解决办法]
1、Linq本身不影响算法，Linq表现好可能有数据样本的问题。
2、最好固定随机数种子，不同的写法才有比较的基础。
3、最好不要把Console.WriteLine放到时间比较里面。
4、数据样本不要有偏好。


static void Main(string[] args)
{
    Random rnd = new Random(0);
    int[] arr = Enumerable.Range(0, 10000000).Select(x => rnd.Next(int.MinValue, int.MaxValue)).ToArray();

    Stopwatch stopwatch = Stopwatch.StartNew();
    var result1 = GetResultLinq(arr);        // 11521 pairs in 12871ms
    Console.WriteLine("Linq: {0} pairs in {1}ms", result1.Count(), stopwatch.ElapsedMilliseconds);

    stopwatch = Stopwatch.StartNew();
    var result2 = GetReresultHashtable(arr); // 11521 pairs in 4201ms
    Console.WriteLine("Hashtable: {0} pairs in {1}ms", result2.Count(), stopwatch.ElapsedMilliseconds);
}

static IEnumerable<int> GetResultLinq(int[] arr)
{
    var arr1 = arr.Distinct().ToArray();
    return arr1.Where(x => x <= 2).Join(arr1.Where(x => x > 2), x => x, x => 5 - x, (x, y) => x);
}

static IEnumerable<int> GetReresultHashtable(int[] arr)
{
    HashSet<int> pool = new HashSet<int>(arr);
    foreach (int i in pool)
    {
        if (i < 3 && pool.Contains(5 - i)) yield return i; 
 
    }
}

[解决办法]
int start = 0, end = arr.Length - 1;
            while (start < end)
            {
                if (arr[start] + arr[end] < 5)
                {
                    start++;
                }
                else if (arr[start] + arr[end] == 5)
                {//找到一个，继续
                    start++;
                    end--;
                }
                else
                {
                    end--;
                }
            }
[解决办法]
http://bbs.csdn.net/topics/390291321看下
1、快速找出一个数组a中的两个数字，使这两个数字之和等于一个给定的值，如果存在，则输出这两个数.不存在则输出"数组中不存在满足条件的两个数"。（30分）
2、将n个正整数存放于一个一维数组a中，试设计一个算法，将所有的奇数移动并存放于数组的前半部分，将所有的偶数移动并存放于数组的后半部分，要求尽可能少地使用临时存储单元，并使计算时间达到O（n）。（40分）
3、为了保证快排序在最坏的情况下也有较高的排序效率，可选待排序序列的第一个元素、最后一个元素和位于中间的一个元素，在三者中选择其值居中的元素，将其交换到待排序序列的第一个元素位置，再做一趟划分。若设整数数组A有n个元素，设计一个函数，实现上述三者取中并交换到待排序序列每一个元素位置的功能。（30分）
答题要求：
1、写出对题目的分析及算法设计过程。
2、用C语言写出算法。
3、对设计的算法进行时间复杂度和空间复杂度分析。

热点排行