[数据结构与算法]力扣刷题--数组1

一：移动零(力扣283）

void moveZeroes(vector<int>& nums) {
        //申请一个辅助数组，存放非零元素，然后再赋值给原数组
        vector<int> aux;
        for(int i=0;i<nums.size();i++){
            if(nums[i]) 
                aux.push_back(nums[i]);//借用向量的push_back函数
        }
        for(int i=0;i<aux.size();i++){
            nums[i]=aux[i];
        }
        //补0
        for(int i=aux.size();i<nums.size();i++){
            nums[i]=0;
        }
    }

很简单的一个思路：

? ? ? ?申请额外数组存储原数组非零元素（利用push_back）,然后赋值回给原数组，最后在末位编变成0

法二：

 void moveZeroes(vector<int>& nums) {
       /*
       原地实现该功能，不申请额外空间：
       定义一个索引k，指向数组第一个元素，i用于遍历数组，如果是非零元素把值赋给k位置。
       k更新到下一个位置，直至遍历结束，从k开始往后补0
       */
        int k=0;//nums中[0,k）存储非零元素
        //for循环，不断把非零元素依次赋值给k
        for(int i=0;i<nums.size();i++)
            if(nums[i]){//nums[i]不为0
                nums[k++]=nums[i];//别忘了移动k索引
            }
        //补零
        for(int i=k;i<nums.size();i++)
            nums[i]=0;
    }

法三：零与非零的交换

void moveZeroes(vector<int>& nums) {
        int k=0;//nums中[0,k）存储非零元素
        for(int i=0;i<nums.size();i++)
            if(nums[i]){
                swap(nums[i],nums[k]);
                k++;
            }
    }

与法二相比，由于直接交换，少了重新赋值为0操作

优化细节：

避免自己和自己交换，可以考虑i与k的大小关系

if(i!=k)? swap(nums[k++],nums[i]);

else k++;

二：挑选颜色

void sortColors(vector<int>& nums) {
        /*
        因为元素只有0,1,2三种可能，所以采用计数排序思想：
        分别统计出：0的个数，1的个数以及2的个数，赋值即可
        */
        int count[3]={0};
        for(int i=0;i<nums.size();i++){
            assert(nums[i]>=0&&nums[i]<=2);
            count[nums[i]]++;//数值直接对应频次
        }
        //定义一个不断累计的索引
        int index=0;
        for(int i=0;i<count[0];i++)
            nums[index++]=0;
        for(int i=0;i<count[1];i++)
            nums[index++]=1;
        for(int i=0;i<count[2];i++)
            nums[index++]=2;
    }

几个代码小细节：

• 因为只有0,1,2且想累计出现个数，直接以元素值计算频次
• 由于从头一次按照个数赋值0,1,2；所以直接建立一个不断累计的index

?其实可以把三路快排的思想移到这

这是最后想达到的效果：

?其实关键在于对遍历索引i的元素处理：

?分以下三种情况：

?如果元素为1，i右移

?如果元素是2，和two前一个元素交换，i不动,two--

?如果元素是1，和zero后元素交换，zero++,i++

代码实现

#include<iostream>
#include<vector>
using namespace std;
class soluction{
public:
   void sortColors(vector<int>& nums){
    /*
    功能实现：
    [0,zero]全是0----也就是zero初始化为-1
    [two,n-1]全是1---也就是two初始化为n(假设nums长度为n)
    索引i遍历数组，遇到1右移，控制(zero,two)范围全是1
    */
   int zero=-1;
   int two=nums.size();
   int i=0;//从头遍历数组
   while( i<two ){//遍历结束条件
       if(nums[i]==1) i++;
       else if(nums[i]==2){
        two--;
        swap(nums[two],nums[i]);
       }
       else{//nums[i]==0
       zero++;
       swap(nums[i],nums[zero]);
       i++;
       }
   }
   }
};
int main(){
   int arr[]={1,0,2,0,2,1,1,2,0};
   vector<int> vec(arr,arr+sizeof(arr)/sizeof(int));
   soluction().sortColors(vec);
   for(vector<int>::iterator it=vec.begin();it!=vec.end();it++)
      cout<<(*it)<<" ";
}

快速排序两种实现

#include<iostream>
#include<vector>
using namespace std;
int partition(vector<int>& a,int L,int R){
    /*
    索引i记录小于基准元素的最后一个位置,初始化为基准元素位置
    索引j用于遍历
    j遇到的元素≥基准元素---往后遍历
    j遇到的元素＜基准元素---交换i后位置和当前位置，i++
    */
   int e=a[L];//以最左边元素为基准元素
   int i=L;
   int j=L+1;
   for(;j<=R;j++){
    if(a[j]<e){
        swap(a[++i],a[j]);
    }
   }
   swap(a[L],a[i]);
   return i;
}
void quickSortHelper(vector<int>& a,int L,int R){
    if(L>=R) return;//递归结束
    int p=partition(a,L,R);
    quickSortHelper(a,L,p-1);
    quickSortHelper(a,p+1,R);
}
void quickSort(vector<int>& a){//一定要加&
    quickSortHelper(a,0,a.size()-1);
}
int main(){
    vector<int> arr={1,22,3,55,66,7,2,11,1,3,4};
    quickSort(arr);
    vector<int>::iterator it;
    for(it=arr.begin();it!=arr.end();it++){
        cout<<(*it)<<" ";
    }
    return 0;
}

注意要在vector加上*，否则原向量不改变

 /*
    双指针法：
    i不断右移，使得其之前的元素均≤基准元素
    j不断左移，使得其之后的元素均≥基准元素
    如果i,j均停止，交换两者所指元素，然后i右移，j左移
    最后----把j位置，即小于基准元素最后一个元素和基准元素交换
    */
   int e=a[L];
   int i=L+1,j=R;//i，j指向除基准元素的两头
   while(1){
      while(i<=j&&a[i]<=e) i++;
      while(i<=j&&a[j]>=e) j--;
      if(i>j) break;
      swap(a[i++],a[j--]);
   }
   swap(a[L],a[j]);
   return j;
}

?三：寻找第k个大的元素

?这里要用到一个快速排序分区的性质：

每次快排后，都可以确定该元素在顺序中的正确位置。

也就是说：排序后，倒数第一个最大，倒数第二个第二大。。。。

只要快排的索引落在了该位置，该位置就可以确定第几大或第几小

 int partition(vector<int>& nums,int l,int r){
        int e=nums[l];
        int i=l;
        int j=l+1;
        for(;j<=r;j++){
            if(nums[j]<e) 
               swap(nums[j],nums[++i]);
        }
        swap(nums[l],nums[i]);
        return i;
    }
    int findKthLargest(vector<int>& nums, int k) {
        int target=nums.size()-k;
        int l=0;
        int r=nums.size()-1;
        while(1){//条件：L<=R,但是该题一定有解，无需判断
          int p=partition(nums,l,r);
          if(p==target) return nums[p];
          else if(p>target) r=p-1;
          else l=p+1;
        }
    }