2021-12-27每日刷题打卡

力扣——排序

75. 颜色分类

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

简单的对数组进行升序排序即可。

class Solution {
public:
    void sortColors(vector<int>& nums) {
        for(int i=0;i<nums.size();i++)
        {
            for(int j=i+1;j<nums.size();j++)
            {
                if(nums[j]<nums[i])
                    swap(nums[j],nums[i]);
            }
        }
    }
};

747. 至少是其他数字两倍的最大数

给你一个整数数组 nums ，其中总是存在 唯一的 一个最大整数 。

请你找出数组中的最大元素并检查它是否 至少是数组中每个其他数字的两倍 。如果是，则返回 最大元素的下标 ，否则返回 -1 。

示例 1：

输入：nums = [3,6,1,0]
输出：1
解释：6 是最大的整数，对于数组中的其他整数，6 大于数组中其他元素的两倍。6 的下标是 1 ，所以返回 1 。

先用哈希表存下每个数字对应的位置，再对数组进行排序，然后比较最后一个数字和倒数第二个数字（即最大的数字和第二大的数字），如果最大的数字是第二大的两倍或更多就通过哈希表返回最大数的原位置下标，否则返回-1。注意要判断一下数组的元素个数，如果只有一个元素那就返回0即可。

class Solution {
public:
    int dominantIndex(vector<int>& nums) {
        if(nums.size()==1)
            return 0;
        unordered_map<int,int>mymap;
        int n=nums.size();
        for(int i=0;i<n;i++)
            mymap[nums[i]]=i;
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                if(nums[j]<nums[i])
                    swap(nums[j],nums[i]);
            }
        }
        return nums[n-1]/2>=nums[n-2]?mymap[nums[n-1]]:-1;
    }
};

1051. 高度检查器

学校打算为全体学生拍一张年度纪念照。根据要求，学生需要按照 非递减 的高度顺序排成一行。

排序后的高度情况用整数数组 expected 表示，其中 expected[i] 是预计排在这一行中第 i 位的学生的高度（下标从 0 开始）。

给你一个整数数组 heights ，表示 当前学生站位 的高度情况。heights[i] 是这一行中第 i 位学生的高度（下标从 0 开始）。

返回满足 heights[i] != expected[i] 的 下标数量 。

示例：

输入：heights = [1,1,4,2,1,3]
输出：3
解释：
高度：[1,1,4,2,1,3]
预期：[1,1,1,2,3,4]
下标 2 、4 、5 处的学生高度不匹配。

先拿一个数组把原数组保存起来，然后对heights进行排序，然后和原数组的相同位置元素对比，如果不相同计数器++，最后返回计数的数。

class Solution {
public:
    int heightChecker(vector<int>& heights) {
        vector<int>v;
        v=heights;
        int n=heights.size(),ans=0,res=0;
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                if(heights[i]>heights[j])
                    swap(heights[i],heights[j]);
            }
            if(heights[i]!=v[i])
                res++;
        }
        return res;
    }
};

1502. 判断能否形成等差数列

给你一个数字数组 arr 。

如果一个数列中，任意相邻两项的差总等于同一个常数，那么这个数列就称为 等差数列 。

如果可以重新排列数组形成等差数列，请返回 true ；否则，返回 false 。

示例 1：

输入：arr = [3,5,1]
输出：true
解释：对数组重新排序得到 [1,3,5] 或者 [5,3,1] ，任意相邻两项的差分别为 2 或 -2 ，可以形成等差数列。

对数组进行排序，然后判断相邻两个数的差值是否都相同，有一个不相同就返回false，如果一直不返回false就返回true。

class Solution {
public:
    bool canMakeArithmeticProgression(vector<int>& arr) {
        int n=arr.size(),ans=0;
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                if(arr[i]>arr[j])swap(arr[i],arr[j]);
            }
            if(i==1)ans=arr[i]-arr[i-1];
            else if(i>1&&arr[i]-arr[i-1]!=ans)return false;
        }
        return true;
    }
};