题目描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。题目链接

<?php

function duplicate($numbers, &$duplication)

{

    // write code here

    //这里要特别注意~找到任意重复的一个值并赋值到duplication[0]

    //函数返回True/False

}

一、暴力破解

1.分析

遍历输入数组，统计元素出现的次数，再遍历一次统计数组，判断出现次数大于1的数字，对 duplication 赋值返回

2.代码

function duplicate($numbers, &$duplication)

{

    if(empty($numbers) || is_null($numbers)) return false;

    $length = count($numbers);

    for($i= 0; $i < $length; $i++) {

        if ($numbers[$i] < 0 || $numbers[$i] > ($length + 1)) {

            return false;

        }

    }

    $count = array_count_values($numbers);

    foreach($count as $key => $val) {

        if ($val > 1){

            $duplication[0] = $key;

            return true;

        } else {

            continue;

        }

        return false;

    }

}

3.复杂度

时间复杂度

代码中有一重循环，因此总的时间复杂度是 O(n)。

空间复杂度

统计元素出现次数时，额外分配了内存，因此空间复杂度是 O(n)。

二、利用现有数组设置标志

1.分析

题目里写了数组里数字的范围保证在0 ~ n-1 之间，所以可以利用现有数组设置标志，

当一个数字被访问过后，可以设置对应位上的数 + n，之后再遇到相同的数时，会发现对应位上的数已经大于等于n了，那么直接返回这个数即可。

以 $numbers = [2,4,3,1,4] 为例：    

$i = 0 时，

    访问了数字 2；

    下标 2；

    2 < 数组长度 5，无操作；

    数组 2 号位上的数 3 < 数组长度 5, 无操作；

    数组 2 号位上的数 3 + 数组长度 5，此时数组为 [2,4,8,1,4]

$i = 1 时，

    访问了数字 4；

    下标 4；

    4 < 数组长度 5，无操作；

    数组 4 号位上的数 4 < 数组长度 5, 无操作；

    数组 4 号位上的数 4 + 数组长度 5，此时数组为 [2,4,8,1,9]

$i = 2 时，

    访问了数字 8；

    下标 8；

    8 > 数组长度 5，此时修改下标 8 - 5 = 3 ；

    数组 3 号位上的数 1 < 数组长度 5, 无操作；

    数组 3 号位上的数 1 + 数组长度 5，此时数组为 [2,4,8,6,9]    

$i = 3 时，

    访问了数字 6；

    下标 6；

    6 > 数组长度 5，此时修改下标 6 - 5 = 1 ；

    数组 1 号位上的数 4 < 数组长度 5, 无操作；

    数组 1 号位上的数 4 + 数组长度 5，此时数组为 [2,9,8,6,9]

$i = 4 时，

    访问了数字 9；

    下标 9；

    9 > 数组长度 5，此时修改下标 9 - 5 = 4 ；

    数组 4 号位上的数 9 > 数组长度 5，重复数字 4 出现，返回 true

2.代码

function duplicate($numbers, &$duplication)

{

    if(empty($numbers) || is_null($numbers)) return false;

    $length = count($numbers);

    for($i= 0; $i < $length; $i++) {

        if ($numbers[$i] < 0 || $numbers[$i] > ($length + 1)) {

            return false;

        }

    }

    for($i = 0; $i < $length; $i++) {

        $index = $numbers[$i];

        if ($index >= $length) $index -= $length;

        if ($numbers[$index] >= $length) {

            $duplication[0] = $index;

            return true;

        }

        $numbers[$index] = $numbers[$index] + $length;

    }

    return false;

}

3.复杂度

时间复杂度

需要遍历一次数组，时间复杂度是 O(n)

空间复杂度

所有操作都是在输入数组上进行的，不需要额外分配内存，空间复杂度为 O(1)

三、利用特性

1.分析

1.把当前序列当成是一个下标和下标对应值是相同的数组；

2.0. 遍历数组，判断当前位的值和下标是否相等：

2.1. 若相等，则遍历下一位；

2.2. 若不等，则将当前位置i上的元素和a[i]位置上的元素比较：若它们相等，则成功！若不等，则将它们两交换。换完之后a[i]位置上的值和它的下标是对应的，但i位置上的元素和下标并不一定对应；

重复2.2的操作，直到当前位置i的值也为i，将i向后移一位，再重复2.0

以数组 $numbers = [2,4,3,1,4] 为例

当 i = 0 时，

    判断 当前位置数字 2 不等于 0；

        当前位置数字 2 不等于 数组 2 号位上数字 3 ，无操作；

        将当前数字 2 和 数组 2 号位上数字 3 互换位置，此时数组为 [3,4,2,1,4];

    判断 当前位置数字 3 不等于 0；

        当前位置数字 3 不等于 数组 3 号位上数字 1 ，无操作；

        将当前数字 3 和 数组 3 号位上数字 1 互换位置，此时数组为 [1,4,2,3,4];

    判断 当前位置数字 1 不等于 0；

        当前位置数字 1 不等于 数组 1 号位上数字 4 ，无操作；

        将当前数字 1 和 数组 1 号位上数字 4 互换位置，此时数组为 [4,1,2,3,4];

    判断 当前位置数字 4 不等于 0；

        当前位置数字 4 等于 数组 4 号位上数字 4，重复数字 4 出现，返回 true

2.代码

function duplicate($numbers, &$duplication)

{

    if(empty($numbers) || is_null($numbers)) return false;

    $length = count($numbers);

    for($i= 0; $i < $length; $i++) {

        if ($numbers[$i] < 0 || $numbers[$i] > ($length+ 1)) {

            return false;

        }

    }

    for($i = 0; $i < $length; $i++) {

        while($numbers[$i] != $i) {

            if ($numbers[$i] == $numbers[$numbers[$i]]) {

                $duplication[0] = $numbers[$i];

                return true;

            }

            $tmp = $numbers[$i];

            $numbers[$i] = $numbers[$tmp];

            $numbers[$tmp] = $tmp;

        }

    }

    return false;

}

3.复杂度

时间复杂度

代码中尽管有一个两重循环，但每个数字最多只要交换 2 次就能找到属于它自己的位置，因此总的时间复杂度是 O(n)。

空间复杂度

所有操作都是在输入数组上进行的，不需要额外分配内存，空间复杂度为 O(1)。

巴特西

【剑指 offer】数组中重复的数字 -- PHP 实现

题目描述

一、暴力破解

1.分析

2.代码

3.复杂度

时间复杂度

空间复杂度

二、利用现有数组设置标志

1.分析

2.代码

3.复杂度

时间复杂度

空间复杂度

三、利用特性

1.分析

2.代码

3.复杂度

时间复杂度

空间复杂度

最新文章

热门文章