2024-07-25 数组排序

数组排序

给定一个整数数组 nums ，按升序对数组进行排序并返回它。

必须在不使用任何内置函数的情况下以 $O(nlog(n))$ 时间复杂度和尽可能最小的空间复杂度解决问题。

输入: 5,2,3,1
输出: 1,2,3,5

解题思路

简单说下思路，题目限定了时间复杂度必须为 $O(nlog(n))$ 。

亮点

• boolean数组，节省空间开销
• 使用 BufferedReader 读取控制台输入，减少时间开销
• 时间复杂度为 O(n)
• 空间复杂度为 O(n)

实现

public class Test007 {

    /**
     * 给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。
     * <a href="https://www.nowcoder.com/practice/fcf87540c4f347bcb4cf720b5b350c76?tpId=295&tqId=2227748&ru=/exam/company&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Fcompany">...</a>
     * 1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
     * 2.假设 nums[-1] = nums[n] =
     * 3.对于所有有效的 i 都有 nums[i] != nums[i + 1]
     * 4.你可以使用O(logN)的时间复杂度实现此问题吗？
     * <p>
     * 输入：[2,4,1,2,7,8,4]
     * 输出：1
     * 4和8都是峰值元素，返回4的索引1或者8的索引5都可以
     *
     * @param args 输入参数
     */
    public static void main(String[] args) {
        int[] nums = {2, 4, 1, 2, 7, 8, 4};
        System.out.println(new Test007().findPeakElement(nums));
    }

    public int findPeakElement(int[] nums) {
        // write code here
        if (nums.length == 1) {
            return 0;
        }
        int size = nums.length;
        int left = 0;
        int right = size - 1;
        // 2 3 4 5 6
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                // 有可能是个峰值
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return right;
    }
}