1、请写一个功能性的函数，输入一个数组，返回这个数组中第二大的数字。要求：只能用一个for循环实现，不能做排序。例如：输入的数组内容是 [3, -1, 2, 8, 4, 1] 返回 4
public static int sort(int[] nums) { if (nums.length < 0) { return 0; } if (nums.length == 1) { return nums[0]; } int tmp,first=nums[0],second=nums[1]; if (first > second) { tmp = second; second = first; first = tmp; } for (int i = 2; i < nums.length; i++) { if (first > nums[i]) continue; else { first = nums[i]; } if (first > second) { tmp = second; second = first; first = tmp; } } return first; }
时间复杂度是O(n)
1.1 额外问题：如果不考虑上述要求的限制，要高效的从给定数组中找出第m大的数字，应该怎样做？数组内容和m都是外部输入的。函数的功能是返回数组中第m大的数字。
如果m的值比较小或者接近数组的长度，那么使用上面的方法实现比较合适。既然又强调了说明一下，估计是考快速排序的算法。思路如下：取第m个数字进行快排，比它大的放到左边，小的放在右边，然后看m的位置i，如果i小于m，那么在m的右边重复查找第m-i大的数字，循环一直到结束。
package com.taobao; import java.util.Arrays; public class Test { public static void main(String[] args) { int[] nums = { 3, -1, 2, 8, 4, 1 }; // System.out.println(Test.sort(nums)); for(int i=1; i<=nums.length; i++) { System.out.println(Test.getMax(nums, i)); } } /** * 获取数组中第几大的数字 * * @param nums * @param index * @return */ public static int getMax(int[] nums, int index) { if(index<1||index>nums.length){ return 0; } int i = 0, j = 0;// 数组下标 int compare = 0, tmp = 0;// 对比值 while (true) { // 对比数值 j = nums.length - 1; compare = nums[index - 1]; for (i = 0; i < j; i++) { if (nums[i] <= compare) { // 比较替换 for (; j > i; j--) { if (nums[j] >= compare) { tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; j--; break; } } } } if ((i+1) == index) { // 找到了 break; } else if (i >= index) { // 继续查找 if (i==j){ nums = Arrays.copyOfRange(nums, 0, i+1); }else{ nums = Arrays.copyOfRange(nums, 0, i); } } else { // 反方向查找 int length = nums.length; nums = Arrays.copyOfRange(nums, i, length); index = index - i; } } return nums[index - 1]; } }