主要元素+有序数组的平方
主要元素
题目:数组中占比超过一半的元素称之为主要元素。给定一个整数数组,找到它的主要元素。若没有,返回-1。
示例 1: 输入:[1,2,5,9,5,9,5,5,5] 输出:5
示例 2: 输入:[3,2] 输出:-1
示例 3: 输入:[2,2,1,1,1,2,2] 输出:2
说明: 你有办法在时间复杂度为 O(N),空间复杂度为 O(1) 内完成吗?
解题思路
我们要找到的主要元素是数组中占比超过一半的元素。因此可以先将数组中的元素排序,如果存在主要元素,那么排序后的中间元素一定是主要元素,然后通过遍历数组统计出和中间元素相等的个数,若超过一半则找到,否则返回-1.
代码展示
代码如下:
class Solution { public: int majorityElement(vector<int>& nums) { sort(nums.begin(),nums.end()); int mid=nums.size()/2; //获得中间位的值 int res=nums[mid]; int n=0; for(int i=0;i<nums.size();i++) { //遍历整个容器获得和中间值相等元素的个数 if(nums[i]==res) n++; } if(n>mid) return res; else return -1; } };
有序数组的平方
题目:给定一个按非递减顺序排序的整数数组 A,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。
示例 1: 输入:[-4,-1,0,3,10] 输出:[0,1,9,16,100]
示例 2: 输入:[-7,-3,2,3,11] 输出:[4,9,9,49,121]
提示: 1 <= A.length <= 10000 -10000 <= A[i] <= 10000 A 已按非递减顺序排序。
解题思路
解法一
暴力解法:我们将数组内的每个数组先平方后排序,最后返回排序后的数组
代码展示
代码如下:
class Solution { public: vector<int> sortedSquares(vector<int>& A) { vector<int> res; for(auto i:A) res.push_back(i*i); sort(res.begin(),res.end()); return res; } }; 执行用时:144 ms, 在所有 C++ 提交中击败了18.60%的用户 内存消耗:25.5 MB, 在所有 C++ 提交中击败了13.79%的用户
解法二
双指针解法:数组其实是有序的, 只不过负数平方之后可能成为最大数了。那么数组平方的最大值就在数组的两端,不是最左边就是最右边,不可能是中间。此时可以考虑双指针法了,i指向起始位置,j指向终止位置。定义一个新数组res,和A数组一样的大小,让k指向res数组终止位置。
如果A[i] * A[i] < A[j] * A[j] 那么res[k–] = A[j] * A[j]; 。 如果A[i] * A[i] >= A[j] * A[j] 那么res[k–] = A[i] * A[i]; 。
代码展示
代码如下:
class Solution { public: vector<int> sortedSquares(vector<int>& A) { vector<int> res(A.size(),0); int k=A.size()-1; for(int i=0,j=A.size()-1;i<=j;) { if((A[i]*A[i])<(A[j]*A[j])) { res[k--]=A[j]*A[j]; j--; } else { res[k--]=A[i]*A[i]; i++; } } return res; } }; 执行用时:52 ms, 在所有 C++ 提交中击败了96.71%的用户 内存消耗:24.6 MB, 在所有 C++ 提交中击败了43.13%的用户