当前位置：首页 > news >正文

1.2数组的基本算法设计

news 2025/6/19 21:38:14

1.移除元素

//整体建表法--通过遍历整个数据集找出所有有效数据原地建表
//时间复杂度o(n),空间复杂度(1)
int removeLen(vector<int>& a ,int value) {
   int k = 0;
   for (int i = 0; i < a.size(); i++) {
       if (a[i] != value) {
           a[k] = a[i];
           k++;
       }
   }
   return k;
}
//元素移动法---覆盖或交换元素原地建表，删除移动元素较少时使用
//时间o(n),空间o(1)
int removeLen(vector<int>& a, int value) {
   int k = 0;
   for (int i = 0; i < a.size(); i++) {
       if (a[i] == value){

   k++;

}
       else {
           a[i - k] = a[i];
       }
   }
   return a.size() - k;
}
//两区间划分法---可以划分为多个区间位置，此位置之前分别为一种状态
//然后从头遍历，属于哪个区间就交换到哪个区间去
int removeLen(vector<int>& a, int value) {
   int k = 0;
   for (int i = 0; i < a.size(); i++) {
       if (a[i] != value) {
           if (k != i) {
               swap(a[i], a[k]);
               k++;
           }
       }
   }
   return k;
}

2.移动0

//整体建表法
void print(vector<int>& nums, int value) {
   int k = 0;
   int i;
   for (i = 0; i < nums.size(); i++) {
       if (nums[i] != value) {
           nums[k] = nums[i];
           k++;
       }
   }
   for (i=k; i < nums.size(); i++) {
       nums[i] = 0;
   }
}
//元素移动法
void print(vector<int>& nums, int value) {
   int k = 0, i;
   for (i = 0; i < nums.size(); i++) {
       if (nums[i] == value) {
           k++;
       }
       else {
           nums[i - k] = nums[i];
       }
   }
   for (i = nums.size() - k; i < nums.size();i++) {
       nums[i] = 0;
   }
}
//区域划分法
//但不能保证非0元素相对位置不变
void print(vector<int>& nums, int value) {
   int k = 0, i;
   for (i = 0; i < nums.size(); i++) {
       if (nums[i] != value) {
           if (k != i) {
               swap(nums[i], nums[k]);
               k++;
           }
       }
   }
   for (i = k; i < nums.size(); i++) {
       nums[i] = 0;
   }
}

3.对数组执行操作（略--同2）

4.三颜色的分类

//区间划分法
void sortColors(vector<int>& nums, int value) {
   int a = 0, i = 0, b = nums.size() - 1;
   for (i = 0; i < nums.size(); i++) {
       if (nums[i] == 0) {
           if (i != a) {
               swap(nums[a], nums[i]);
           }
           a++;
       }
       else if (nums[i] == 2) {
           if (i != b) {
               swap(nums[i], nums[b]);
           }
           b--;
       }
   }
}

5.轮转数组

void reverse(vector<int>& nums, int first, int end) {
   while (first < end) {
       swap(nums[first], nums[end]);
       first++;
       end--;
   }
}
//元素交换法----对于给定的k中后面k个元素为a[n-k,n-1],前面n-k个元素为a[0,n-k-1],通过归纳发现规律进行处理数组a
void rotate(vector<int>& nums, int k) {
   int n = nums.size();
   int k = k % n;
   //将前元素逆置，后元素逆置，前后合并元素逆置
   reverse(nums, 0, n - k - 1);
   reverse(nums, n - k, n - 1);
   reverse(nums, 0, n - 1);
}