知识点
1 快速排序
优点：平均性能好，通常是实际排序应用中最好的选择
思路：采用分治的思想。将数组划 A[p,r] 划分成两个子数组A[p,q-1],A[q+1,r]和一个数A[q]，使得子数组1中的所有数均小于等于A[q],子数组2中的所有数均大于等于A[q].
代码：
if(p<r)
{
q=partition(A,p,r);
quicksort(A,p,q-1);
quicksort(A,q+1,r);
}
核心代码：寻找q，即选择主元
partition(A,p,r)
x = A[r];
i = p-1;
for j=p to r-1;
if(A[j]<=x)
{
i=i+1;
exchange A[i] with A[j]
}
excahnge A[i+1] with A[r]
return i+1;
6 题目描述
给定一个 24 小时制（小时:分钟?"HH:MM"）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。
class Solution {
public:
int f(string a){
return (a[0]*10+a[1])*60+a[3]*10+a[4];
}
int findMinDifference(vector<string>& timePoints) {
vector<int>nums;
for(auto it:timePoints){
nums.emplace_back(f(it));
nums.emplace_back(f(it)+1440); //将一天变成两天
}
sort(nums.begin(),nums.end());
int jie=INT_MAX;
for(int i=0;i<nums.size()-1;i++) {
jie=min(jie,nums[i+1]-nums[i]);
}
return jie;
}
};
7 题目描述
给定由一些正数（代表长度）组成的数组?A，返回由其中三个长度组成的、面积不为零的三角形的最大周长。
如果不能形成任何面积不为零的三角形，返回?0。
class Solution {
public int largestPerimeter(int[] A) {
Arrays.sort(A);
for(int i = A.length - 1; i >= 2; i--) {
int a = A[i];
int b = A[i - 1];
int c = A[i - 2];
if(a < b + c){
return a + b + c;
}
}
return 0;
}
}
8 题目描述
第?i?个人的体重为?people[i]，每艘船可以承载的最大重量为?limit。
每艘船最多可同时载两人，但条件是这些人的重量之和最多为?limit。
返回载到每一个人所需的最小船数。(保证每个人都能被船载)。
class Solution {
public:
int numRescueBoats(vector<int> &people, int limit) {
int ans = 0;
sort(people.begin(), people.end());
int light = 0, heavy = people.size() - 1;
while (light <= heavy) {
if (people[light] + people[heavy] > limit) {
--heavy;
} else {
++light;
--heavy;
}
++ans;
}
return ans;
}
};
练习题
1 题目描述??912.排序树组
给你一个整数数组?nums，请你将该数组升序排列。
class Solution {
public:
vector<int> sortArray(vector<int>& nums)
{
int length=nums.size();
for(int i=0;i<length;i++)
{
for(int j=length-1;j>i;j--)
{
int temp=0;
if(nums[i]>nums[j])
{
temp=nums[j];
nums[j]=nums[i];
nums[i]=temp;
}
}
}
return nums;
}
};
2 题目描述?169.多数元素
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于?? n/2 ??的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
class Solution {
public:
int majorityElement(vector<int>& nums) {
//建立哈希数组找其中出现次数大于n/2的数
unordered_map<int,int> hash;
int res=0;
int len=nums.size();
for(int i=0;i<len;i++){
hash[nums[i]]++;
if(hash[nums[i]]>len/2){
res=nums[i];
break;//优化一下
}
}
return res;
}
};
3 题目描述?217.存在重复元素
给定一个整数数组，判断是否存在重复元素。
如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
sort(nums.begin(), nums.end());
for(int i=0;i<nums.size()-1;i++)
{
if(nums[i]==nums[i+1])
{
return true;
}
}
return false;
}
};
4 题目描述??
给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
如果数组元素个数小于 2，则返回 0
class Solution {
public:
int maximumGap(vector<int>& nums) {
int n = nums.size();
if (n < 2) {
return 0;
}
int exp = 1;
vector<int> buf(n);
int maxVal = *max_element(nums.begin(), nums.end());
while (maxVal >= exp) {
vector<int> cnt(10);
for (int i = 0; i < n; i++) {
int digit = (nums[i] / exp) % 10;
cnt[digit]++;
}
for (int i = 1; i < 10; i++) {
cnt[i] += cnt[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
int digit = (nums[i] / exp) % 10;
buf[cnt[digit] - 1] = nums[i];
cnt[digit]--;
}
copy(buf.begin(), buf.end(), nums.begin());
exp *= 10;
}
int ret = 0;
for (int i = 1; i < n; i++) {
ret = max(ret, nums[i] - nums[i - 1]);
}
return ret;
}
};
5 题目描述
给定一个非负整数数组?A，返回一个数组，在该数组中，?A?的所有偶数元素之后跟着所有奇数元素。
你可以返回满足此条件的任何数组作为答案。
class Solution {
public:
vector<int> sortArrayByParity(vector<int>& nums) {
int i=0;//头指针
int j=nums.size()-1;//尾指针
while(i<j){//头小于尾
if(nums[i]%2==0){//如果第一个数是偶数就往后继续判断
i++;//因为他要求的就是偶数放在前面
}
else{
int a=nums[i];//交换两个值，不解释傻子都会
nums[i]=nums[j];
nums[j]=a;
j--;//每次换完之后都会跟下一个减一去交换
}
}
return nums;//返回数组
}
};
|