【一个算法题】一起来写一把。
题目：
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);
}
假设经过排序，有以下数组：
-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，跳出，因为已经小了。
......
就这样，一直左右交替，避免递归，因为你这个毕竟不是尾递归。编译器不能对其堆栈数据进行优化。
这个和你的是不是有点相似？我大致看了你的算法，没有仔细看，但是感觉到你用到递归，所以不是很理想。
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);
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());
}
}
}
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());
}
}
}
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;
}
}
}
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;
}
}
[其他解释]
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();
我觉得优化的地方在于：
因为 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，需要的负数是几，然后从头部进行循环比较，比到类似的情况，跳出，然后继续比较右侧正数。等会我来举个例子
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);
}
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);
????????}
}
}
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());
}
}
}
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;
}
}
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);
Console.WriteLine("Linq: {0} pairs in {1}ms", result1.Count(), stopwatch.ElapsedMilliseconds);
stopwatch = Stopwatch.StartNew();
var result2 = GetReresultHashtable(arr);
Console.WriteLine("Hashtable: {0} pairs in {1}ms", result2.Count(), stopwatch.ElapsedMilliseconds);
}
static IEnumerable<int> GetResultLinq(int[] arr)
{
HashSet<int> pool = new HashSet<int>(arr);
return pool.AsParallel().Where(x => x < 3 && pool.Contains(5 - 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;
}
}
{
start++;
}
else if (arr[start] + arr[end] == 5)
{//找到一个，继续
start++;
end--;
}
else
{
end--;
}
}
[其他解释]
楼主把问题弄复杂了，有序的数组不需要用递归就可以找到你要的数对。O(N)就可以了。
[其他解释]
设数组长度为N
bucket［N］这个时候bucket是一个链表，
根据数组的值bucket［array［i］%N].add(array[i])
for(i = 0 ; i < N ; i ++) {
x = 5 - i; //x为i对应的哪个桶 i＝ 3 ,x = 2, i = -2,x=7
//遍历桶链表同上
}
下面就是遍历桶
//伪代码
for(i = 0 ; i < 20 ; i ++) {
x = 5 - i; //x为i对应的哪个桶 i＝ 3 ,x = 2, i = -2,x=7
if (bucket［i < 0 ? 20 + i : i］ //i桶这个位置存在
&& bucket［x< 0 ? 20 + x : x］//x桶存在
) {
//anything
}
}
