在数组中找到第二大的数

Myth丶恋晨 2024-02-18 20:24 102阅读 0赞

### 题目 ###

在数组中找到第二大的数

你可以假定至少有两个数字

您在真实的面试中是否遇到过这个题？  
样例  
给出 \[1, 3, 2, 4\], 返回 3.

给出 \[1, 2\], 返回 1.

### 解答 ###

public class FindTwo {
        
    
        public static void main(String[] args) {
            int[] nums = {
       6, 3, 6, 2, 56, 123};
            System.out.println(secondMax(nums));
        }
    
        /**
         * 找出第二大的数
         *
         * @param nums
         * @return
         */
        public static int secondMax(int[] nums) {
            // write your code here
            int[] sortResult = quickSort(nums, 0, nums.length - 1);
            return sortResult[nums.length-2];
        }
    
        /**
         * 快速排序
         *
         * @param nums
         * @param low
         * @param high
         * @return
         */
        public static int[] quickSort(int[] nums, int low, int high) {
            if (low >= high) {
                return nums;
            }
            int mid = subSort(nums, low, high);
            quickSort(nums, low, mid);
            quickSort(nums, mid + 1, high);
            return nums;
        }
    
        /**
         * 交换位置，返回分割点
         *
         * @param origin
         * @param low
         * @param high
         * @return
         */
        public static int subSort(int[] origin, int low, int high) {
            int splitNum = origin[low];
            while (low < high) {
    
                //从后往前
                while (origin[high] >= splitNum && high > low) {
                    high--;
                }
                origin[low] = origin[high];
                //从前往后
                while (origin[low] <= splitNum && high > low) {
                    low++;
    
                }
                origin[high] = origin[low];
            }
            origin[high] = splitNum;
            return high;
        }
    }