阵列验证 - 不使用辅助数组 [英] array validation - without using an auxiliary array

问题描述

这个问题是真正的brainiacs，因为它应该没有辅助阵列来完成
并且必须是最有效的！

This question is for real brainiacs, cause it should be done without an auxiliary array and has to be most efficient!

C程序 - 需要收到以X号的数组
（假设X = 4数组：5,4,3,2）
并检查阵列拥有所有从0到X-1的数字
（如果X是44，它需要，如果0之间的所有号码进行检查，43数组中）。

C program - needs to recieve an array with X numbers (suppose X=4 array : 5,4,3,2) and check if the array has all the numbers from 0 to X-1 (If X is 44 it needs to check if all numbers between 0 to 43 inside the array).

它是超级有效的！ - 我的意思是，在阵列上运行的43倍是不是一种选择

It has to be super efficient - I mean, running on the array 43 times is not an option!

你有什么想法如何做到这一点？我试图找出这一个小时，没有任何成功！

Do you have any idea how to do this?? I'm trying to figure this one for hours without any success!!

它必须是O（N）。

推荐答案

我不明白我缺少这个问题，但据我所知，我不明白了一个道理，为什么任何（合理的）解决方案应该是任何东西更多 - /比worse- O（N）时间（和空间）的复杂性。

I don't understand what I'm missing in this question but AFAIK I don't see a reason why any (reasonable) solution should be anything more-/worse- than O(n) time (and space) complexity.

从上面的意见和答案，我的理解如下：

From the above comments and answers, I understand the following:

• 负数：我不知道负数是否允许。该任择议定书说检查所有的数组都从0开始编号，以X-1 。所以，任何小于 0 预计不会在数组中为止。所以，我认为负数不允许


• 重复号码：指从OP相同报价 - 检查所有的数组都从0到X-1 我想，如果<$ C $的数字C> X 是数组的大小，并从 0 到 X-1 应该是present时，我想没有重复的数字是不允许的。



• Negative numbers : I'm not sure whether negative numbers are allowed or not. The OP says check if all the array has all the numbers from 0 to X-1. So anything less than 0 is not expected in the array. So I assume negative numbers are not allowed
• Duplicate numbers : referring to the same quote from the OP - check if all the array has all the numbers from 0 to X-1 I guess if X is the size of the array and all numbers from 0 to X-1 should be present, the I guess no duplicate numbers are allowed.

于是作出上述假设，我们可以使用一个位来检查是否 I （ 0℃= I＆LT; = X-1 ）是present与否。如果 I 是重复的，然后它会失败提的是，有一个重复号码。

So making the above assumptions, we can use one bit to check whether i (0 <= i <= X-1) is present or not. If i is duplicate then it will fail mentioning that there is a duplicate number.

它会扫描整个数组一次 - O（N），只使用每元一位，所以 X 是 10 > X 位所需要的百万元素和的sizeof（INT）是 4 那么我们就需要 3.82中号的内存来存放数组元素和仅 0.48M 用于存储元素的presence。

It scans the whole array one time - O(n) and just uses one bit per element, so X is 10 the X bits are needed - for example consider we need to handle 1000000 elements and sizeof(int) is 4 then we need 3.82M of memory to hold the array elements and only 0.48M is used for storing the presence of an element.

#include <stdio.h>

#define X 10
#define MIN 0
#define MAX X-1

int main(void)
{
    //int arr[X] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
    //int arr[X] = {6, 7, 8, 9, 0, 5, 3, 2, 11, 12};
    //int arr[X] = {1, 1, 2, 4, 5, 6, 7, 8, 2, 2};
    int arr[X] = {1, 3, 2, 4, 5, 6, -7, 8, 2, 2}; 

    /* if X is more than sizeof(int) then change 
       the flag type to a wider one! */
    int flag = 0;

    int i;

    for(i=0 ;i<X ; i++) {
        if (arr[i] >= MIN && arr[i] <= MAX) {
            if (flag & 1<<arr[i]) {
                printf("Duplicate found : %d \n", arr[i]);
                return -1; 
            }   
            flag |= 1<<arr[i];
        } else {
            printf("Failure at %d : %d \n", i, arr[i]);
            return -1; 
        }   
    }   

    printf("Success \n");

    return 0;
}

这篇关于阵列验证 - 不使用辅助数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！