You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

1051.高度检查器-Height Checker

. 1 min read

1051.高度检查器-Height Checker

题目描述:

学校在拍年度纪念照时,一般要求学生按照 非递减 的高度顺序排列。

请你返回至少有多少个学生没有站在正确位置数量。该人数指的是:能让所有学生以 非递减 高度排列的必要移动人数。

Example:

示例:

输入:[1,1,4,2,1,3]
输出:3
解释:
高度为 4、3 和最后一个 1 的学生,没有站在正确的位置。

提示:

  1. 1 <= heights.length <= 100
  2. 1 <= heights[i] <= 100

Analysis

题目仅要求返回移动人数,即与非递减排列的 Hamming Distance

因此将传入数组与排序后的数组对比即可

Solution  ( 3ms)

执行用时 : 3 ms, 在Height Checker的Java提交中击败了100.00% 的用户

内存消耗: 34.1 MB, 在Height Checker的Java提交中击败了100.00% 的用户

class Solution {
    public int heightChecker(int[] heights) {
        int[] auxArr = Arrays.copyOf(heights, heights.length);
        Arrays.sort(auxArr);
        int diff = 0;
        for (int i=0; i<heights.length; i++) {
            if (auxArr[i] != heights[i]) {
                diff++;
            }
        }
        return diff;
    }
}

复杂度分析

时间:O(NlogN)

空间:O(N)