阅微客栈

注册或登录 (丢失密码?):

用户名：
密码：

记住我

阅微客栈 » 头脑风暴

1. 

   zhang
   神

   An array A[1...n] contains all the integers from 0 to n except one. In this problem, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is "fetch the jth bit of A[i]", which takes constant time. Find the missing integer in O(n) time.

   发布于 1 年 之前 #
2. 

   521zheng
   Member

   先排序，A[A[i]-1]和A[i]交换位置(O(n))，再看看哪个数A[i]!=i-1,missing is i+1,repeat is A[i]

   发布于 8 月 之前 #
3. 

   Wanting
   Member

   我觉得应该是做xor操作

   发布于 8 月 之前 #
4. 

   521zheng
   Member

   偶测试过的最好的算法
   int finddupandmissing(int a[], int N, int &dup, int& mis)
   {

   for(int i=0; i<N; i++)
   {
   if((a[i]-1)!=i)
   {
   swap(a[a[i]-1], a[i]);
   }
   }

   for( i=0;i<N;i++)
   {
   if((a[i]-1)!=i && a[a[i]-1]==a[i])
   {
   dup=a[i];
   mis = i+1;

   break;
   }

   }
   return 0;
   }

   发布于 7 月 之前 #
5. 

   lemonutzf
   Member

   判断第一位是0 or 1，并计数，根据计数和n的奇偶性来判断缺失的数所在的集合
   继续判断第二位。。。。。

   复杂度 n + n/2 + n/4 + .. < 2n

   发布于 7 月 之前 #
6. 

   cyberyao
   Member

   to lemonutzf

   没有看懂，能详细点么

   发布于 1 月 之前 #

该主题的 RSS Feed

回复

你必须 登录 后发帖。