一道微软面试题，嘛叫打点？

Question

说有一组数, 都为整型, 最小为1, 最大为255, 中间可能有重复的数字, 请尽量用时间复杂度最小的算法判断这组数中是不是有重复.
这是一道算法题，我当时没给出最优解，面试官说是打点方法，什么是打点方法？具体原理是什么，举个例子吧，谢谢，

Answer 1

你就说你用sql写来这个程序 
保证没复杂度

Answer 2

好像一条sql语句就能搞定了吧。算法么排序后判断相邻两个数字是不是相等即可。

Answer 3

弄一个 int[256] 的数组，遇到一个数字就在数组标记一下，也许这就叫“打点”？？

Answer 4

我觉得已经说得够具体了，先生命一个数组 int flag[256];全部置0， 遇到一个数字，比如23，就 flag[23]++;标记一下，如果flag[23]>1了，就说明有重复

Answer 5

正解。对提议用sql的表示无语。下次考排序，你告诉他调Sort函数就行了？

Answer 6

估计是某个算法的E文把上回有人在qq上问我：“卡吃是啥，他说他面试的时候，面试官总问他啥是卡吃”我想了半天，才反应过来是cache不过貌似我现在还不知道E文名是“打点”的算法这哪个来着

Answer 7

#include<stdio.h>
int main()
{
int temp,a[256],i;
for(i=0;i<256;i++)
{
a[i]=0;
}
for(i=0;i<256;i++)
{
scanf("%d",&temp);
if(a[temp]==0)a[temp]=1;
else {
printf("%d\n",temp);
}
}
return 0;
}
这样？

Answer 8

是这种方法嘛?            int[] a = { 1, 2, 8, 1, 7, 9, 6, 79, 82, 92, 64, 154, 154, 221, 85, 96, 241, 64, 42, 131, 22, 11, 9 };
            int[] b = new int[256] ;
            string s = string.Empty;
            foreach (int ai in a)
            {
                if (b[ai] != 1)
                    b[ai] = 1;
                else
                    s += ai+";";//s为重复的
            }

Answer 9

晕！把.net软件的所有数据和功能都放到关系数据库里边，只能说明你沉迷于关系数据库，并不代表适合广义的软件开发。

Answer 10

孩子不好意思 我在VS2010 .NET3.5环境下,编译通过才发上来的

Answer 11

和Set用来统计单词出现的次数差不多吧

Answer 12

int[] a = { 1, 2, 8, 1, 7, 9, 6, 79, 82, 92, 64, 154, 154, 221, 85, 96, 241, 64, 42, 131, 22, 11, 9 };
int[] b = new int[256] ;
for(int i=0;i<a.length;i++)
{
  if(b[a[i]]==0)
  {
    b[a[i]]=a[i] //打点?
  }
  else
  {
    已被赋值过一次
  }
}

Answer 13

好方法，这就是为什么说int类型还告诉你1～256的原因吧

Answer 14

老题目了好吧...
c++区里问过的..
int aa[256]; 都初始化0.然后然后每个数,作为数组下标. aa[5]++之; 全部搞完后, aa[x]>1的就是重复超过1次的数了啊

Answer 15

排序?新申请空间?不需要
这样做:
for (int i=0;i<len;i++) {
while(true){
if(arr[i] == arr[arr[i]]){
//输出重复
break;
}
if(arr[i] == i){
break; //已在所在位置
}
swap(i, arr[i]); //放到对应位置
}
}
时间复杂度:看似双重循环,实际复杂度几乎为O(n)
空间复杂度:O(1)

Answer 16

for (int i=0;i<len;i++) {
while(true){
if(arr[i] == arr[arr[i]]){
//输出重复
break;
}
if(arr[i] == i){
break; //已在所在位置
}
swap(i, arr[i]); //放到对应位置 
}
}

Answer 17

    public class Infection
    {
        static int N = 1;
        static int men = 1;
        public static void Main(String[] args)
        {
            while (true)
            {
                men = 1;
                string s = Console.ReadLine();
                if (s == "q")
                    break;                N = int.Parse(s);
                infection(N);   
                Console.WriteLine("第" + N + "天共有" + men + "个人被感染！");
                Console.WriteLine("************************************");
            }
        }        //public static void infectionOld(int totalDay)
        //{
        //    int day;
        //    if (totalDay <= 5)
        //    {
        //        return;
        //    }        //    if (totalDay > 5 && totalDay <= 10)
        //    {
        //        for (day = 6; day <= totalDay; day++)
        //        {
        //            men = men + 3;
        //        }
        //    }
        //    else
        //    {
        //        for (day = 6; day <= 10; day++)
        //        {
        //            men = men + 3;
        //            infection(totalDay - day + 1);
        //            infection(totalDay - day + 1);
        //            infection(totalDay - day + 1);
        //        }        //        men--;
        //    }
        //}        public static void infection(int totalDay)
        {
            int day;
            if (totalDay <= 5)
                return;            for (day = 6; day <= totalDay; day++)
            {
                if (day > 10)
                {
                    men--;
                    break;
                }     
                
                men = men + 3;
                infection(totalDay - day + 1);
                infection(totalDay - day + 1);
                infection(totalDay - day + 1);
            }
        }
    }

Answer 18

是不是和UDP打点差不多啊  

Answer 19

a = array();
a[1] = array(1,1,1,1,1)
a[2] = array(2,2,2,)
a[3] = array(3)
....
a[255] = array(255)现在找 3 是不是有重复的.count(a[3] )  = 1 无现在找 1 是不是有重复的
count(a[1]) > 1  : 有 

Answer 20

if(n>255)
   cout<<"有重复"<<endl;
else
 {
   建立一个255个字符的数组。从给定数组做循环
   分别放到以当前数组值为索引的数组上，如果当前值为0则写入。若不为0则说明是重复的。
 }
不知道表达清楚没有。

Answer 21

我感觉打点的意思就是在一个板子上打一个洞。
具体到这个题目中：
由于最大的数十255，所以我们可以用bitmap的方法来做。
首先声明一个数组unsigned int a[8];这个数组中刚好有256位，每位标识一个数，起始时各位置零；
然后扫描要处理的数组，遇到一个数就将它放到相应的位中，这个可以用位运算来完成；
扫描的过程中遇到一位为0，则将其置1，如果遇到1，则说明此处的数字有重复，程序退出即可。

Answer 22

位图方法和上面的C#代码，思想是一样的，鉴定完毕，至于上面的Java解法正在研究~

Answer 23

个人观点：
首先不懂你的arr是不是指输入数组，如果是的话，那你这个代码好像有问题。
假设int[] arr = { 256, 2, 8, 1, 7, 9, 6, 79, 82, 92, 64, 154, 154, 221, 85, 96, 241, 64, 42, 131, 22, 11, 9 };
那么i=0时,arr[arr[i]]=arr[256]，IndexOutOfBoundsException...如果你指的arr是
int[] arr = new int[256];
那么输入数组在哪？

Answer 24

if( (select count(distanct (id) ) from table  = 255))
begin
 print '没有重复'
end
else
begin
 print '有重复'
edn

Answer 25

是不是把问题想复杂了？如果讲数组排序，然后再进行排查看是否有重复的，那么排序的时间，不就是浪费掉了么？
a[255]为需要排查的数组。   for i = 1 to 255 
     if   a[i-1] = a[i]   then 
        '有重复的数
        return true 
     end if 
   next i    '没有重复的数
   return false 
      

Answer 26

上次在中视在线国际传媒广告（北京）有限公司 面试JAVA开发经理，那总监问我熟悉钩S不？真汗颜你们知道什么叫钩S不?

Answer 27

a[256],b[256];
int j = 0;
for(int i = 0;i < n;i++)
{
if (b[i] > a[j])
{
a[j] = b[i];
j++;
}
if (b[i] == a[j])
{
i 重复
}
if (b[i] < a[j])
{
for (int zxii = 0;zxii < j;zxii++)
{
if (b[i] == a[zxii])
{
i重复
}
}
}
}

Answer 28

回77楼,
早上测了下,
arr是源数组,此方法在arr长度大于255时有效
另外,两个 break 条件位置写反了

Answer 29

“打点”算法：有一组数, 都为整型, 最小为1, 最大为255, 中间可能有重复的数字, 请尽量用时间复杂度最小的算法判断这组数中是不是有重复.
先声明一个数组 int flag[256];全部置0， 遇到一个数字，比如23，就 flag[23]++;标记一下，如果flag[23]>1了，就说明有重复

Answer 30

借花献佛
int[] a = { 1, 2, 8, 1, 7, 9, 6, 79, 82, 92, 64, 154, 154, 221, 85, 96, 241, 64, 42, 131, 22, 11, 9 };
int[] b = new int[256] ;
for(int i=0;i<a.length;i++)
{
  b[a[i]]=b[a[i]]+1;
  if (b[a[i]]>1)
   {
       “哈哈有重复的了”
   }
}
循环一次

Answer 31

        static void Main(string[] args)
        {
            const int MAX = 270;//源数组大小
            const int iBitCount = 32;
            int resut = 0;            int[] item = new int[MAX];//要处理的数组（源数组）
            Random rnd = new Random();
            uint[] num = new uint[(MAX+iBitCount-1)/iBitCount];//位数组            //初始化源数组
            for (int i = 0; i < MAX;i++)
            {
                item[i] = rnd.Next(1, 255);//取1-255随机数初始源数组
                Console.Write( i + "-" + item[i]+"\r\n" );
            }            //找重复
            for (int j = 0; j < MAX; j++)
            {                if (((num[item[j] / iBitCount]) & (1 << (item[j] % iBitCount))) != 0)
                {
                    resut=j;
                    break;
                }
                else
                {
                    num[item[j] / iBitCount] |= (uint)1 << (item[j] % iBitCount);
                }            }
            if (resut != 0)
            {
                Console.Write("重复的数字：" + item[resut]);
                Console.Write("\r\n数组位置：" + resut);
            }
            else
            {
                Console.Write("没有重复的数字！");
            }
            Console.ReadLine();
            
        }

Answer 32

说说我的看法，献丑了假设原数组A[n],在定义一个整形数字B[255],那么，遍历一次数组A，是得数组B[A[i]]=1,即打点。最后，SUM数组B，如果SUM值等于n，则没有重复数值，否则有重复数值。

Answer 33

楼上认真回答问题的思路正确，但按本题要求，25、71楼正解，97楼是DEMO，可以直接运行