说明：记录刷剑指offer，使用php与python两种语言，对解题思路以及涉及到的基本语法以及知识点做学习记录。其中对于每道题目进行粗略的分类。
题目来源
- 分类：数组
- 数组中出现重复的数字
题目描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
解题思路（参考剑指offer 第二版）
- 方法一：暴力直接的结果方法，双循环，计数统计次数，此中方法时间复杂度为 O(n^2)
- 方法二：把输入的数组排序，之后从头到尾扫描排序后的数组即可，排序一个长度为n的数组需要O(nlogn)的时间
- 方法三：哈希表解决，从头到尾顺序扫描数组的每个数字，每扫到一个数字的时候，可以使用O(1)的时间判断哈希表是否存在该数字，没有加入哈希表，存在即找到了一个重复的数字。算法复杂度为O(n),但提高时间效率是以空间为代价的。
- 方法四：利用数组数字的特性，因为所有的数字都在0到n-1之间，如果数组中没有重复的元素，则数组排序后，第i个位置值即为i。由于数组中有重复的数字，所以有些位置与此位置的值存在不匹配的现象。
具体思路：重新排这个数组，从头到尾扫描这个数组中的每个数字，当扫描到下标尾i的数字时，首先比较这个数字（用m表示）是否等于i。如果i == m，则直接扫描下一个数字；如果i != m, 则需要拿此位置的数m与数组的第m个数字比较。如果此数字与第m个数字相等则找到了第一个重复的数字（此数字在i和m位置都出现了）；如果不想等，就把第i个位置的数m与第m个位置的数字交换，把m放在应该放的位置上，之后重复比较、交换的过程，直至发现一个重复的数字。
例如：{2,3,1,0,2,5,3} ，数组名为nums
i = 0 时 nums[i] = 2 ， nums[i] != i 交换数字 nums[i] nums[nums[i]]即交换nums[0] 与 nums[2] ,结果为[1,3,2,0,2,5,3];
此时第0个数字是1，仍与下标本相等，继续把它和下标为1的数字交换，结果为[3,1,2,0,2,5,3];
第0个数字是3，仍与下标本相等，继续把它和下标为3的数字交换，结果为[0,1,2,3,2,5,3];
此时第0个位置数与此下标相等，接下来的数字中，下标1，2，3的3个数都与下标相等，所以不需要执行任何操作，接下来扫描下标为4的数字2，由于下标与其数值不想等，需要和下标为2的数字比较，此时数组中下标为2的数字也是2，因此找到一个重复的数字。
编程实现
PHP
<?php
运行时间：30ms
占用内存：2504k
function duplicate($numbers, &$duplication)
{
//这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
//函数返回True/False
$length = count($numbers);
if (empty($numbers) || $length <= 0):
return false;
foreach ($numbers as $item) {
if ($item < 0 || $item > $length - 1) {
return false;
}
}
for ($i = 0; $i < $length; $i++ ) {
while ($i != $numbers[$i]) {
if($numbers[$i] == $numbers[$numbers[$i]]){
$duplication[0] = $numbers[$i];
return true;
}
$temp = $numbers[$i];
$numbers[$i] = $numbers[$temp];
$numbers[$temp] = $temp;
}
}
}
?>
Python
# -*- coding:utf-8 -*-
class Solution:
def duplicate(self, numbers, duplication):
# write code here
if not numbers or len(numbers) <= 0:
return False
for num in numbers:
count = 0
for item in numbers:
if num == item:
count += 1
if count > 1:
duplication[0] = item
return duplication[0]
break
return False
# 运行时间：29ms
#
# 占用内存：5736k
def duplications(self, nums, dups):
if not nums or len(dups) <= 0:
return False
for i in range(len(nums)):
if (nums[i] < 0 ) or (nums[i] > len(nums) - 1):
return False
for i in range(len(nums)):
while i != nums[i]:
if nums[i] == nums[nums[i]]:
dups[0] = nums[i]
return True
temp = nums[i]
nums[i] = nums[temp]
nums[temp] = temp
return False
s = Solution()
print s.duplicate([2,1,3,0,4], [0])
print s.duplications([2,3,1,0,2,5,3], [0])
知识点总结
- php引用传递参数
调用一个函数，只能有一个返回值，（除非你返回的是一个数组，数组里就可以包含多个值，但严格来说，这也是只能返回一个值，一个数组）。
但你调用函数，需要返回二个值时，使用引用传递就间接达到这个目的。
