codility之PermCheck

PermCheck

题目:


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, because value 2 is missing.

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

Write a function:

    function solution($A);

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.


大致是判断数组A是不是一个连续的数组;
要求:
最差的时间复杂度为O(N);
最差空间复杂度O(N);

如何解决?

和上一次的FrogRiverOne基本一样, 不再多说。

代码:


function solution($A) {
    // write your code in PHP5.5
    $map = array();
    $count = 0;
    $len = count($A);
    foreach ($A as $k => $v) {
        if ($v > $len) {
            return  0;  
        }   
        if (!isset($map[$v])) {
            $map[$v] = 1;
            $count += 1;
        }   
    }   

    if ($count == $len) {
        return  1;  
    }   

    return  0;  
}

可能的坑就在于没有判断$v是不是已经能够超过了数组A的长度, 如果超过了数组长度,

按照permutation的定义:

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

数组A肯定不是一个permutation了, 所以我们直接返回0即可。

Leave a Reply

Your email address will not be published. Required fields are marked *


To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax