using System;
namespace MinABS
{
class Program
{
static void Main(string[] args)
{
int n = 100;
int[] a = new int[n];
Random rand = new Random();
int min = int.MaxValue;
int max = int.MinValue;
Console.WriteLine("产生了" + n + "个数据的实验数组,");
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();
}
}
}
分享到:
相关推荐
给定一个整数数组,其中元素的取值范围为0到10000,求其中出现次数最多的数。
现在有一个简单游戏:给你一行n个整数,要求你在两两之间放入“+”、“-”、“*”、“/”等符号共n-1个,使得表达式计算结果最大且不包含数字k。 请注意: 1) 表达式自左向右运算,不考虑优先级,例如:6+7*11=143;...
给定2到15个不同的正整数,你的任务是计算这些数里面有多少个数对满足:数对中一个数是另一个数的两倍。 比如给定1 4 3 2 9 7 18 22,得到的答案是3,因为2是1的两倍,4是2的两倍,18是9的两倍。 输入形式 输入...
小Q今天在上厕所时想到了这个问题:有n个数,两两组成二元组,差最小的有多少对呢?差最大呢? 输入描述: ...对于每组数据,输出两个数,第一个数表示差最小的对数,第二个数表示差最大的对数。
数字字母特殊字符两两混合正则表达式1
数字字母特殊字符两两混合正则表达式
多个样本的非参数检验的两两比较精.pdf多个样本的非参数检验的两两比较精.pdf多个样本的非参数检验的两两比较精.pdf多个样本的非参数检验的两两比较精.pdf多个样本的非参数检验的两两比较精.pdf
给定n个正整数,请问它们两两之间的绝对值之差的和为多少?
这个函数接收一个整数数组arr和数组的长度n为参数,并对数组进行升序排序。通过使用两个嵌套的循环结构,本程序对数组中的元素两两比较,并交换它们的位置,直到所有元素被正确排序。 在main函数中,程序声明了一个...
NOIP普及组近5年NOIP试题分析,全国青少年信息学奥林匹克竞赛
输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。 这个题目完成的思路有很多,很多排序算法都可以完成既定操作,关键是复杂度性的考虑。以下几种思路当是笔者...
读入一组整数到vector对象,头尾元素两两配对(第一个和最后一个,第二个和倒数第二个),计算每对元素的和.用C++语言描述。
/*冒泡排序-----从大到小 ...*每一循环都会从待排序的数中找出一个最小值,排到这组数据的最末端或首段,即冒泡 *对于n个数冒泡排序的最大趟数是n - 1,每一趟排序都会在这组待排序的数中产生一个最小值, */
(两两相连的房间问题)一所奇怪的房子,这所房子里有n个房间,每个房间里有一些门通向别的房间,可是这些门十分奇怪,它们只能从房间a开向房间b,也就是说,一扇从a开向b的门是不能让一个人从b房间走到a房间的。...
1.6.3. 输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数 位于数组的后半部分 ...........................................................130 1.6.4. 给定链表的头指针和一个...
一种基于两两组合测试的fit框架扩展,如何使用fit进行持续集成测试的方法
(两两相连的房间问题)一所奇怪的房子,这所房子里有n个房间,每个房间里有一些门通向别的房间,可是这些门十分奇怪,它们只能从房间a开向房间b,也就是说,一扇从a开向b的门是不能让一个人从b房间走到a房间的。...
多个样本率的卡方检验及两两比较--之-spss-超简单.docx
费了将近一周的时间,把孙啸老师的《生物信息学基础》第三章中的序列两两比对基本算法彻底搞明白了,为了促进生物信息学的普及,特奉献个大家共享。
如果一个序列满足下面的性质,我们就将它称为摆动序列: 1. 序列中的所有数都是不大于k的正整数; 2. 序列中至少有两个数。 3. 序列中的数两两不相等; 4. 如果第i – 1个数比第i – 2个数大,则第i个数比...