yulu

算法-找数

发表于

题目：已知0到n（n为正整数）之间缺少1个数，找出缺少的数。

基数解法：
分析：
step1: 0到n在正常情况下有n+1个元素，但是缺少一个元素，我们可以先补全

1
arr[n] = -1

然后开始循环，
step2:在循环的过程中要进行交换，交换就要确定交换的条件：
若 一个数已经在正确的位置中，那就没必要交换
若 一个索引的value值为-1，那也没必要交换

整体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
<?php
/**
*   Copyright (C) pianke 2017 All rights reserved.
*
*   FileName      ：test.php
*   Version       ：1.0
 */
$li = [0,1,2,3,4,5,6,8,9];
$count = count($li);
$li[$count] = -1;
//step1 for li
for($index = 0; $index < $count; $index++){
	//step2 get value by index
	$value = $li[$index];
	//$li[$index] = -1;
	while(1){
		if($value == -1 || $li[$value] == $value){
		//if($li[$value] == $value){
			$li[$index] = $value;
			break;
		}else{
			//swap
			$tmp = $li[$value];
			$li[$value] = $value;
			$value = $tmp;
		}
	}
}
print_r($li);

解法2:
1到n正常的所有元素之和是能得到的，然后用和挨个减去给的序列就好了。比较取巧

解法3:
根据异或的原理来处理 例如：

1
a^b^c^a^b = c

拓展：1到n中缺了一个数，多了一个数，找出来
解法：根据基础解法的思路处理，给定的序列元素个数是正常的，那我们就不用补数了。