快速排序Python版

算法 ,
答案 # coding: utf-8 def quick_sort(arr, low, high): # 继续排序的条件是low小于high if low < high: # 将数组分成左右两个区,并返回分区的位置 part_index = partition(arr, low, high) # 递归排序左边的数组 # 这里直接在arr上原地排序,所以不占用额外空间 quick_sort(arr, low, par…

什么情况下快速排序最慢?

算法
答案 这个得看pivot(基准元素或枢轴)的选择策略。 如果选择最左面或最右面的元素作为基准元素,那最坏的情况就会在: 数组已经是正序排过序的。 数组已经是倒序排过序的。 所有的元素都相同(1、2的特殊情况)。 因为这些案例在用例中十分常见,所以这个问题可以通过要么选择一个随机的基准…

从数组中查找最小的k个元素PHP版

PHP ,
答案 思路: 假设最前面的1000个数为最小的,算出这1000个数中最大的数,然后和第1001个数比较 如果这个最大的数比第1001个数小的话,跳过 如果这个最大的数比第1001个数大则将两个数交换位置,并算出新的1000个数里面的最大数 再和下一个数比较,以此类推 /** * 从数组里找出最小的 $k 个数 …

求n以内的质数PHP版

PHP , ,
答案 质数筛选定理: n不能够被小于等于根号n的任何质数整除,则n是一个质数 除了2,其他偶数都不是质数 /** * 求n以内的质数 * @param $n int 质数的最大范围 * @return array 质数集合 */ function primeNumber($n) { $prime = array(2); // 2为质数 for ($i = 3; $i <= $n; $i += 2) { /…

打乱数组元素PHP版

PHP ,
答案 function shuffleArray($arr) { $n = count($arr); for ($i = 0; $i < $n; $i++) { $randPos = mt_rand(0, $n - 1); if ($randPos != $i) { $temp = $arr[$i]; $arr[$i] = $arr[$randPos]; $arr[$randPos] = $temp; } } return $arr; } 测试代码: $arr = [1, 2, 3, 4, 5, 6, 7, 8]; …

查找两个有序数组的相同元素PHP版

PHP , ,
答案 function findArrayCommon($arr1, $arr2) { $common = array(); $i = 0; $j = 0; $count1 = count($arr1); $count2 = count($arr2); while ($i < $count1 && $j < $count2) { if ($arr1[$i] < $arr2[$j]) { $i++; } elseif ($arr1[$i] > $arr2[$j]) { $j++; } else …

反转数组PHP版

PHP , ,
答案 function reverseArray($arr) { $n = count($arr); $left = 0; $right = $n - 1; while ($left < $right) { $temp = $arr[$left]; $arr[$left++] = $arr[$right]; $arr[$right--] = $temp; } return $arr; } 测试代码: $arr = [11, 22, 33, 44, 55, 66, 77]; // 输出:[77,66,55,44,…

反转单向链表Java版

算法 , ,
答案 public class Node { public int value; public Node next; public Node(int value) { this.value = value; } public Node reverseList(Node head) { Node prev = null; // 用于暂存前面的节点 Node next = null; // 用于暂存后面的节点 while (head != null) { next = head.next; // 把…

查找两个大文件(1G以上)的相同内容PHP版

PHP , ,
答案 这是是一个大文件处理,面试官出题的意图并不希望你两层for循环进行遍历,这种答案肯定是不会要的! 这道题目的解法思路是: 顺序读取两个文件的的全部记录 将每条记录经过hash->转换为10进制->%n后存到10个文件中,这样一共2G的数据分成10份,每份就是204.8M,低于内存限制 我可以…