说明：记录刷剑指offer，使用php与python两种语言，对解题思路以及涉及到的基本语法以及知识点做学习记录。其中对于每道题目进行粗略的分类。
题目来源
- 分类：数组
- 数组中出现超过一半的数字
题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
题目分析（此题采用不排序的方法）
数组排序
排序后位于数组中间的数字一定是出现次数超过数组长度一半的元素。
不排序，根据数组特点解决问题
数组中一个数字出现次数超过数组长度的一半，那么它出现的次数比其他所有数字出现次数的总和还要多。因此，遍历数组时保留两个值：1.数组中的一个数字；2.出现次数。当遍历下一个数字的时候，如果下一个数字和之前保存的数字相同，则次数加1；如果下一个数字和之前保存不同，则次数减1。如果次数为0，这时需要保存下一个数字，并把数字次数设为1。由于要找的数字比其他数字出现的次数之和还要多，所以要找到最后一次把次数设为1对应的数字。
补充：
- 对于上述的解析，可以完成基本功能找到符合要求的数字，但是我们还需要考虑解决一些无效输入的问题。
- 需要考虑输入数组中出现频率最高的数字都没有达到出现次数超过数组长度一半的标准。
- PHP实现如下：
运行时间：160ms
占用内存：2436k
<?php
$r_inputInvaild = false;
function MoreThanHalfNum_Solution($numbers)
{
if(CheckInvalidArray($numbers)){
return 0;
}
$result = $numbers[0];
$times = 1;
for($i = 1; $i < count($numbers); $i++){
if ($times == 0) {
$result = $numbers[$i];
$times = 1;
} elseif ($result == $numbers[$i]){
$times++;
} else {
$times--;
}
}
// 使用foreach也是可以的
// foreach ($numbers as $key => $value) {
// if($key == 0){
// continue;
// }
// if ($times == 0) {
// $result = $value;
// $times = 1;
// } elseif ($result == $value){
// $times++;
// } else {
// $times--;
// }
// }
if(!CheckMoreThanHalf($numbers,$result)){
$result = 0;
}
return $result;
}
function CheckInvalidArray($numbers){
$r_inputInvaild = false;
if (empty($numbers) || count($numbers) <= 0) {
$r_inputInvaild = true;
}
return $r_inputInvaild;
}
//输入数组中出现频率高的数组没有达到超过数组长度一半的标准
function CheckMoreThanHalf($numbers,$result){
$times = 0;
foreach ($numbers as $item) {
if($item == $result){
$times++;
}
}
$isMoreThanHalf = true;
if($times * 2 <= count($numbers)){
$isMoreThanHalf = false;
$r_inputInvaild = true;
}
return $isMoreThanHalf;
}
var_dump(MoreThanHalfNum_Solution(array(1,2,3,2,2,2,5,4,2)));
?>
- python实现
运行时间：37ms
占用内存：5724k
# -*- coding:utf-8 -*-
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
# write code here
length = len(numbers)
if not numbers or length <= 0:
return 0
# 初始一个长度为10，全是0的数组
arr = [0 for i in range(10)]
for i in numbers:
arr[i] = arr[i] + 1
for j in range(0, 10):
if arr[j] > length / 2:
return j
return 0
知识总结复
- php foreach跳出循环 continue；
