977. 有序数组的平方

first try

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
    vector<int> result;
    for(int i=0;i<A.size();i++)
    {
        int tmp=A[i];
        result.push_back(tmp*tmp);
    }
    sort(result.begin(),result.end());
    return result;
    }
};

C++知识补充：范围for语句

for(declaration : expression)
    statement
  • 要求expression必须是一个能够返回迭代器begin和end成员的序列类型（数组、初始化列表、vector和string等等）
  • 要求declaration定义一个变量，满足序列中的每个元素都能转换成该变量的类型（auto）
  • 如果需要对序列中的元素执行修改写操作，需要把循环变量声明成引用类型
  • 每次迭代都会重新定义循环控制变量，并将其初始化为序列的下一个值，随后执行statement
class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        vector<int> result;
        for(int num:A)
        {
            result.push_back(num*num);
        }
        sort(result.begin(),result.end());
        return result;
    }
};

better solution

第一种方法没有利用到题目中整数数组A为非递减排序的条件，需要使用sort()快排，我们可以利用双指针避免。

由于整数数组A非递减排序，那么以第一个非负数为界，向左序列的数的平方递增，向右序列的数的平方也递增，我们只需要使用双指针分别向两边走并不断把较小的数加入结果序列并重点关注边界的情况即可：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int boundary=-1;
        for(int i=0;i<A.size();i++){
            if(A[i]<0)
            {
                boundary++;
            }
            else
                break;
        }
        vector<int> result;
        int i = boundary , j = boundary+1;
        while(i>=0||j<A.size()){
            if(i<0){
                result.push_back(A[j]*A[j]);
                ++j;
            }
            else if(j==A.size()){
                result.push_back(A[i]*A[i]);
                --i;
            }
            else if(A[i]*A[i]<A[j]*A[j]){
                result.push_back(A[i]*A[i]);
                --i;
            }
            else {
                result.push_back(A[j]*A[j]);
                ++j;
            }
        }
        return result;
    }
};

1365. 有多少小于当前数字的数字

first try

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> result;
        for(int i=0;i<nums.size();i++){
            int count=0;
            for(int j=0;j<nums.size();j++){
                if(j != i){
                    if(nums[j]<nums[i]){
                        count++;
                    }
                }
            }
            result.push_back(count);
        }
        return result;
    }
};