微软面试题，求数组中两两之差绝对值最小的值,研究了好几天,写出来一个看起来象O(n)的算法,终于搞清楚了C#二进制的一些关键操作了.
研究了好几天,写出来一个看起来象O(n)的算法,O(nlog)就不用写了.
using System;namespace MinABS{ class Program { static void Main(string[] args) { int n = 1000; int[] a = new int[n]; Random rand = new Random(); int min = int.MaxValue; int max = int.MinValue; Console.WriteLine("产生了" + n + "个数据的实验数组,"); Console.WriteLine("本程序适用于int.MinValue到int.MaxValue范围，请自行修改输入的量和范围"); for (int i = 0; i < n; i++) { //赋值并且取到最大最小值 a[i] = rand.Next(int.MinValue, int.MaxValue); //a[i] = rand.Next(-100, 100); if (a[i] < min) { min = a[i]; } if (a[i] > max) { max = a[i]; } Console.Write(a[i] + " "); } Console.WriteLine(); Console.WriteLine("在O(n)内得到最大最小分别是："); Console.WriteLine(max + "和" + min); long offset = (long)max + Math.Abs((long)min); //规划数组的长度。每个byte有8位长 int len = (int)(offset >> 3) +1 ; Byte[] B = new Byte[len]; int kkkk = 0; bool IsSame = false;//是否有重合点标记 //O(n)的时间内分配到了Byte[]中。 for (int i = 0; i < n; i++) { offset = (long)a[i] - (long)min; int index = (int)(offset >> 3); int temp = B[index]; //把末k位变成1 //把右数第k位变成1 例如：(00101001->00101101,k=3) x | (1 << (k-1)) int tempOffSet = (1 << ( (int)(offset & 7) ) ); //判断重合 if (!IsSame) { kkkk = temp & tempOffSet; if ((temp & tempOffSet) >= 1) { IsSame = true; //如果0算最小距离就在这里退出吧。本代码判断重合，但没把0作为结果。 } } int bbb = B[index]; B[index] |= (Byte)(tempOffSet); int aaa = B[index]; } //最小距离初始为最大。 Console.WriteLine("在O(n)的时间内分配到了Byte[]中，正在计算最小距离，请稍候。。。。。"); long minABS = long.MaxValue; long lastIndex = -1; //在常数范围内循环，复杂度不增加。最坏的情况是32*int.MaxValue次。 for (int i = 0; i < B.Length; i++) { if (B[i] == 0) { continue; } //在常数范围内循环，复杂度不增加。 for (int k = 0; k < 8; k++) { if (((B[i] >> k) & 1) == 1) { if (lastIndex >= 0) { long temp = ((long)i << 3) + k - lastIndex; if (temp < minABS) { minABS = temp; Console.WriteLine("目前得到了最小距离：" + minABS); } } lastIndex = (i << 3) + k; } } } if (IsSame) { Console.WriteLine("有重合点"); } else { Console.WriteLine("无重合点"); } Console.WriteLine("不考虑重合最小距离是：" + minABS); Console.WriteLine("总复杂度是：O(n)"); Console.ReadLine(); } }}
“ //在常数范围内循环，复杂度不增加。最坏的情况是32*int.MaxValue次。”
这个要多大的内存空间呢
其它的我没细看，好像是将整个范围划分为一个个桶
[解决办法]
这个不叫O(n)的算法
[解决办法]
看的很迷惑，不知道你的算法本质是什么。
我很希望你能用简单的方法介绍下，看代码比看算法痛苦很多！
我实在没心情看下去了，而且我对C#没感情，如果可以请用 C++ 或 C 编写，感激不尽。。。。。
[解决办法]
先排序一下，再把头尾四个放到一起，在排一下。
再去头尾。
或者，两个数组先排序然后并起来，再首尾向减掉。
算法能到 O(log(n)) ，如果是已经排序的，那就是常数时间了。
[解决办法]
所谓的O(N)的都是利用了数据本身的分布规律/信息量来的，你不知道分布，怎么就叫他O（N）？
Hash表通常比较快，可是如果发生碰撞的次数很大，还会O（1）的时间查找么。
[解决办法]
求数组A = {a1, a2, ... an}两两之差绝对值最小的值，我的感觉是可以构造减法序列B = {b1, b2, ..., bn-1}，其中b(i) = a(i+1) - a(i)，通过扫描B中的符号反转求和来做，具体算法不写了。
[解决办法]
概念有错误吧？
对输入 int array[n];
你的算法的复杂度好像是 O(max(array[n])-min(array[n])), 时间空间复杂度都是吧
举个例子 输入 int array[4]={最小的整数，0, 100, 最大的整数};
你的算法要分析完所有的 2^24 (16M)各内存单元才能得出结果，与数组的size n有什么关系呢？
按你的限定和前提下， max(array[n])-min(array[n])<=2^32, 是个常数，那你的算法的复杂度都是O(1)了。 :)
[解决办法]
好像不太对，，，
[解决办法]
楼主的算法可以针对double类型的数组吗？好像取的是int型。
我有一个O(n)的算法，且很容易理解、很容易实现（代码量极少），但是空间需求很大，并且无法针对非整型。如下：
1、设这些整数的范围为a-b，那么建立一个数组，数组大小为（b－a＋1），清0数组。于是，在这个范围内的每一个整数都对应于一个数组元素。
2、扫描一遍所有整数，每遇到一个整数，就将与其对应的数组中那个位置的数组元素加1。
3、扫描数组，计算相邻两个1之间的0的个数，取最小值min，所以，min+1就是最后的答案；
若扫描过程中遇到大于1的数字，则说明有重复整数，那么立即返回0。
[解决办法]
为了降低上述算法的空间复杂度，可以换数组为bit，即每个整数现在其实是对应于1个bit：
取一定量的内存，清0，然后扫描一遍整数的时候，将对应的bit置为1；若发现已经为1，则立即返回0。
这样可以将上述算法的空间复杂度降低到1/32，但增加了对置位时该bit是否为0的判断。