Task description

A non-empty zero-indexed array A consisting of N integers is given.

A permutation is a sequence containing each element from 1 to N once, and only once.

For example, array A such that:

    A[0] = 4

    A[1] = 1

    A[2] = 3

    A[3] = 2

is a permutation, but array A such that:

    A[0] = 4

    A[1] = 1

    A[2] = 3

is not a permutation.

The goal is to check whether array A is a permutation.

Write a function:

int solution(int A[], int N);

that, given a zero-indexed array A, returns 1 if array A is a permutation and 0 if it is not.

For example, given array A such that:

    A[0] = 4

    A[1] = 1

    A[2] = 3

    A[3] = 2

the function should return 1.

Given array A such that:

    A[0] = 4

    A[1] = 1

    A[2] = 3

the function should return 0.

Assume that:

N is an integer within the range [1..100,000];

each element of array A is an integer within the range [1..1,000,000,000].

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Copyright 2009–2014 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

Solution  C:42

#define FLAG(N) (((N)>>30)&0x3)
#define VALUE(N)  ((N)&(0xffffffff>>2))
#define SET_FLAG(N, flag) ((N)|((flag)<<30))
#define NOT_VISITED 0
#define VISITED 1
 
int solution(int A[], int N)
{
    int notFound = N;
    char* reason = "good";
    int  i = 0;
    for( i = 0; i < N; i++ )
    {
        int value = VALUE(A[i]);
        if(value > N)
        {
            // 数字超过N,不可能是全排列
            reason = "overflow";
            break;
        }
        int next = value - 1;
        if( FLAG(A[next]) == NOT_VISITED )
        {
            A[next] = SET_FLAG( A[next], VISITED);
            notFound --;
        }
        else
        {
            // 出现重复的元素, 不可能是全排列
            reason = "duplicate";
            break;
        }
    }
    //printf("reason:%s", reason);
    return (notFound == 0);
}

寻求更好地解法

本文出自 “技术-另类的爱情” 博客，请务必保留此出处http://randywang.blog.51cto.com/4247710/1435004