面试难题：数组 size-n 包含来自 [i, i + n)

Question

给定一个未排序的数字数组，编写一个函数，如果数组由连续数字组成，则返回 true。

示例：

1. 如果数组为 {5, 2, 3, 1, 4}，则该函数应返回 true，因为该数组具有从 1 到 5 的连续数字。

2. 如果数组为 {83, 78, 80, 81, 79, 82}，则该函数应返回 true，因为该数组具有从 78 到 83 的连续数字。

3. 如果数组为 {34, 23, 52, 12, 3 }，则该函数应返回 false，因为元素不连续。

4. 如果数组是 {7, 6, 5, 5, 3, 4}，则该函数应返回 false，因为 5 和 5 不连续。

我想出了以下算法：

1. 查找数组的最大值和最小值

2. max-min+1应该是数组的大小

3. 检查重复项

4. 检查之间的所有连续数字

我怎样才能实现第四条路径？（复杂度应为O(n)）

非常欢迎其他建议。

Answer 1

如果输入数组是 A：

1. 求 A 的最小值和最大值，如果数组大小错误，则返回 False。

2. 创建一个相同大小的新数组 B，最初全为零

3. 对于每个索引 i，让 B[ A[i] - min] = 1。

4. 检查 B 是否仍包含任何零。

每一步都需要 O(n) 时间。

Answer 2

int visited[max - min + 1];

for(c = min; c <= max; c++) {
    visited[array[c] - min] += 1;

    if(visited[array] > 1)
        return false;               // since this is a duplicate
}

这应该没问题。 Visited[] 记录原始数组中的数字出现的次数。如果它的任何元素大于 2，则存在重复项，因此返回 false；
由于两个数组的大小都是 max-min+1，因此在循环结束时，visited[] 已满，因为我们访问了 array[] 的所有元素。所以它访问的是空的，一定有重复的地方，但我们不需要打扰，因为那时我们仍然返回 false。

Answer 3

bool consecutive(int a[], size_t n)
{
    int min = find_min(a,n);
    int max = find_max(a,n);

    if (max - min + 1 == n) {
        // variant of counting sort, O(n)
        // note: never freed, don't use in production
        int *freq = calloc(sizeof(int), n);

        for (size_t i=0; i<n; i++)
            if (++freq[a[i] - min] > 1)
                return false;
        return true;
    }
    return false;
}

Answer 4

在我看来，这可以在 O(n) 时间内完成，并具有 O(1) 额外空间。

确定数组的最小值和最大值。如果 (max - min + 1) != n，则返回 false。

从数组中的每个元素中减去 min。我们现在有一个包含 [0, n) 范围内的 n 个元素的数组。我们现在只需检查是否有重复项。这可以通过如下代码在线性时间内完成（每个元素最多移动一次）：

for (int i = 0; i != n; ++i)
{
    if (A[i] != i)
    {
        int temp = A[i];
        for (;;)
        {
            int index = temp;
            if (A[index] == index)
            {
                // We have a duplicate
                return false;
            }
            std::swap(temp, A[index]);
            if (index == i)
            {
                // A[i] now contains i
                break;
            }
        }
    }
}
// If we get to here, there are no duplicates

Answer 5

我不太擅长C，但是你需要做第4步吗？当然，如果 2 为真并且没有重复项，那么它包含该序列，否则它不包含该序列？

Answer 6

正如您所要求的，您的算法中的第四步根本不需要（因为#2和#3将保证它们是连续的）

我们可以通过执行所有操作来保存算法的更多比较（以提高其时间复杂度）单次遍历的步骤：

int is_consecutive(int *a, int size)  // O(n) algo
{   
 int min, max;
 hash H;
 if(!a || size == 0 ) return -1;
 max=min=a[0];
 H.insert(a[0]);

 for(i=1; i<size; i++) {
   if(H.find(a[i]) { delete H; return 0; }  // duplicacy check
   else H.insert(a[i]);
   if(a[i] < min) min = a[i];
   else if(a[i] > max) max = a[i];
 }
 if(size != (max - min)) { delete H; return 0; }  //range = size check
 delete H;   
 return 1;
}

Answer 7

这是适用于 1..N 的东西，你可以使用算术级数论坛来调整这个 [i,i+n]

// gcc -Wall q1.cc -o q1 && q1                                                                          

//Given an array of size N in which every number is between 1 and N, write a simple program to determine
//if there are any duplicates in it.                                                                    

//answer                                                                                                
/* The numbers can be assumed to not be stored in sorted order.  We also assume that all numbers are    
between 1 and N inclusive.  If for example they are not, then we will return true indicating that there 
is a possibility of a duplicate.                                                                        

This can be implemented using a bit array of size N all initialized to 0.  as we iterate the input array
of numbers, we simply check if the bit array at that number index is set, if so, we return true.  if not
we set the bit.  we loop until we get to the end of the list, and if we get there, that means no        
duplicate was found, and we can return false.                                                           

However, the above algorithm has the problem of using extra space.  A better idea is to take advantage  
of the fact that we are guaranteed that the numbers are between 1 and N.  if we were to use the fact    
that the arithmetic sum of these numbers is equal to n(n+1)/2, then we can just sum up all the numbers  
and ensure that it equals the above sum.  If it does, we have no duplicate, else we do.                 
*/                                                                                                      

#include <stdio.h>                                                                                      
#include <assert.h>                                                                                     

bool any_dup(const int *a, int n)                                                                       
{                                                                                                       
        int req_sum = n*(n+1)/2;                                                                        

        int s = 0;                                                                                      
        for (int i = 0;i<n;i++)                                                                         
                s += a[i];                                                                              

        return (s != req_sum);                                                                          
}                                                                                                       


int main()                                                                                              
{                                                                                                       
        int a[]={1,2,3,4,5};                                                                            
        assert(!any_dup(a,5));                                                                          

        int b[]={1,2,2,3,3,4,5,6};                                                                      
        assert(any_dup(b,8));                                                                           

        int c[]={5,2,3,1,4};                                                                            
        assert(!any_dup(c,5));                                                                          

        int d[]={34,21,1,4,2};                                                                          
        assert(any_dup(d,5));                                                                           

        return 0;                                                                                       
}                                                                                                       

Answer 8

求数组中的最小元素、最大元素以及元素之和。

它们形成一个艺术级数，元素的总和为： (no.Of element/2)*(2*minElement+(n-1)*differnce)

差值为 1

在这种情况下，如果 sum==(array.length/2)* 则 (2*minElement+(array.length-1)*1) && maxElement==(minElement+(lenght ofArray-1)*1)

那么数字是连续的。

没有额外的空间复杂度，时间复杂度为 O(n)

感谢 @jpalecek 的纠正。现在应该没问题了