面试时间：2019 年 11 月 4 日，星期一，下午两点。
1. 给定一个二维数组，数组每一行从左到右都是递增的，每一列也是递增的。请完成一个函数，输入为如上二维数组和一个整数，函数功能为判断该整数是否存在于数组中。时间复杂度尽可能的低。（请说明你的算法的复杂度。）
下面是一个例子：
二维数组：
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
数字：9
<?php
$array = [
[1, 2, 8, 9],
[2, 4, 9, 12],
[4, 7, 10, 13],
[6, 8, 11, 15],
];
$number = 9;
/**
* 最简单的方法就是遍历整个数组
* 时间复杂度 O(Row*Column-1)
*/
function findNumberInArray($array, $number) {
foreach ($array as $rowArray) {
foreach ($rowArray as $value) {
echo $value, " ";
if ($number == $value) {
return true;
}
}
}
return false;
}
/**
* 从二维数组的左下角开始逐行查找
* 时间复杂度 O(Row+Column-1)
*/
function findNumberInArray2($array, $number) {
$minRow = 0;
$minColumn = 0;
$maxRow = count($array) - 1;
$maxColumn = count($array[0]) - 1;
if ($number < $array[0][0] || $number > $array[$maxRow][$maxColumn]) {
return false;
}
for ($row = $maxRow; $row >= $minRow; $row--) {
for ($column = $minColumn; $column <= $maxColumn; $column++) {
echo $array[$row][$column], " ";
if ($array[$row][$column] == $number) {
return true;
}
if ($array[$row][$column] > $number) {
break;
}
if ($array[$row][$column] < $number) {
$minColumn = $column + 1;
}
}
}
return false;
}
/**
* 从二维数组的右上角开始逐行查找
* 时间复杂度 O(Row+Column-1)
*/
function findNumberInArray3($array, $number) {
$minRow = 0;
$minColumn = 0;
$maxRow = count($array) - 1;
$maxColumn = count($array[0]) - 1;
if ($number < $array[0][0] || $number > $array[$maxRow][$maxColumn]) {
return false;
}
for ($row = $minRow; $row <= $maxRow; $row++) {
for ($column = $maxColumn; $column >= $minColumn; $column--) {
echo $array[$row][$column], " ";
if ($array[$row][$column] == $number) {
return true;
}
if ($array[$row][$column] > $number) {
$maxColumn = $column - 1;
}
if ($array[$row][$column] < $number) {
break;
}
}
}
return false;
}
echo "/**
* 最简单的方法就是遍历整个数组
* 时间复杂度 O(Row*Column-1)
*/\n";
for ($number = 0; $number <= 15; $number++) {
echo "find ", $number, ": ";
findNumberInArray($array, $number);
echo "\n";
}
echo "/**
* 从二维数组的左下角开始逐行查找
* 时间复杂度 O(Row+Column-1)
*/\n";
for ($number = 0; $number <= 15; $number++) {
echo "find ", $number, ": ";
findNumberInArray2($array, $number);
echo "\n";
}
echo "/**
* 从二维数组的右上角开始逐行查找
* 时间复杂度 O(Row+Column-1)
*/\n";
for ($number = 0; $number <= 15; $number++) {
echo "find ", $number, ": ";
findNumberInArray3($array, $number);
echo "\n";
}2.把数组最开始的若干个元素搬到数组末尾，称为数组的旋转。给定一个递增数组的旋转数组，请完成一个函数，时间复杂度尽可能的低，输出该旋转数组的最小元素。并给出复杂度。
例如输入数组（4，5，6，7，8，10，1，2，3），输出 1。
<?php
$array = [4, 5, 6, 7, 8, 10, 1, 2, 3];
/**
* 使用 min() 函数
* 时间复杂度：O（N）
* 源码：https://github.com/php/php-src/blob/master/ext/standard/array.c
*/
echo min($array), "\n";
/**
* 使用二分查找法
* 时间复杂度：O(log2N)
*/
function findMinimumNumberInArray($array, $start = 0, $end = null) {
if ($end == null) {
$end = count($array) - 1;
}
if ($start == $end) {
return $array[$start];
}
$middle = floor(($start + $end) / 2);
if ($array[$start] < $array[$end]) {
return findMinimumNumberInArray($array, $start, $middle);
} else {
return findMinimumNumberInArray($array, $middle, $end);
}
}
echo findMinimumNumberInArray($array), "\n";3.输入一个字符串，输出该字符串中字符的所有组合。（不限编程语言，请注明你选择的语言）
下面是一个例子：
输入参数：字符串：“abc”
输出：“a”, “b”, “c”, “ab”, “ac”, “bc”, “abc”
<?php
$string = "abc";
$length = strlen($string);
/**
* 使用二进制表示不同的排列组合
*
* 0 0 1 a
* 0 1 0 b
* 0 1 1 ab
* 1 0 0 c
* 1 0 1 ac
* 1 1 0 bc
* 1 1 1 abc
*/
for ($i = 1; $i < 1 << $length; $i++) {
for ($j = 0; $j < $length; $j++) {
if ($i & (1 << $j)) {
echo $string[$j];
}
}
echo "\n";
}参考：
127 total views, 7 views today
