目錄
一：題目
二：方法1-直接遍歷
三：方法2-空間換時間
四：方法3-雙指標移動
總結：
一：題目
由示例可以得知：不需要考慮超出新長度后面的元素，且在長度范圍內的元素順序可以任意，
二：方法1-直接遍歷
遍歷陣列，將要洗掉元素后面的元素往前覆寫，
注意：覆寫后，要在原位置開始判斷，所以覆寫后，要抵消掉for回圈中的i++，
當要洗掉的是最后一個元素時，不進入內部的for回圈，直接執行numsSize--，i-- ，然后不滿足外層回圈i<numsSize條件 跳出回圈，
方法1 遍歷陣列，把val后的元素往前覆寫
int removeElement(int* nums, int numsSize, int val)
{
int i = 0;
int j = 0;
for (i = 0; i < numsSize; i++)
{
if (nums[i] == val)
{
//把val后面的元素往前覆寫，所以j的位置在i的后面
for (j = i + 1; j < numsSize; j++)
{
nums[j-1] = nums[j];
}
//刪掉了一個元素
numsSize--;
i--; //與for回圈中的i++抵消
//減一后再加一，再次比較被洗掉元素的下標現在所對應的元素
}
}
return numsSize;
}當陣列中一半的元素都是要洗掉的元素，時間復雜度為：O(N*N)
三：方法2-空間換時間
以空間換時間
1.動態開辟一個與原陣列一樣大小的空間
2.使用兩個變數，如果指向的元素不是要洗掉的元素，就把元素移到新陣列，如果指向的時要洗掉的元素，就指向下一個元素繼續判斷是否為要洗掉的元素
3.最后再把新陣列的內容拷貝回原陣列 ，
4.最后把動態開辟的空間釋放掉，指標置空，防止記憶體泄漏！
題目已經說明：不需要考慮超出新長度后面的元素
//方法2：空間換時間
int removeElement(int* nums, int numsSize, int val)
{
int* arr = (int*)malloc(sizeof(int) * numsSize);
if (arr == NULL)
{
printf("malloc fail\n");
return 0;
}
int i = 0;
int j = 0;
//1.若指向的內容不是val，就移到新陣列
for (i = 0; i < numsSize; i++)
{
if (nums[i] != val)
{
arr[j] = nums[i];
j++;
}
}
//2.再把新陣列的內容拷貝回去
for (i = 0; i < j; i++)
{
nums[i] = arr[i];
}
//3.釋放掉空間，防止記憶體泄漏
free(arr);
arr = NULL;
//4.j就是洗掉后的元素個數
return j;
}
空間復雜度：O(N) 開辟了一個大小一樣的陣列
時間復雜度: O(N) 需要遍歷陣列比較
四：方法3-雙指標移動
使用雙指標，遍歷陣列進行移動，在一個陣列中實作
1.定義兩個變數，一個變數src用來移動，一個變數dst用來存盤資料，
2.當src指向的不是要刪的元素，把arr[src]放到arr[dst]的元素，src++，dst++
當src指向的是要刪的元素，dst不動，src++
3.最后dst的數值就是陣列新長度
//方法3：使用雙指標，在一個陣列中實作
int removeElement(int* nums, int numsSize, int val)
{
//如果src指向的不是要洗掉的元素就放到dst位置，src++ dst++
//如果src指向的是val 就++一下跳到下一個元素繼續判斷
int src = 0;
int dst = 0;
int i = 0;
for (i = 0; i < numsSize; i++)
{
if (nums[src] != val)
{
nums[dst] = nums[src];
dst++ ;
src++;
}
else
{
src++;
}
}
return dst;
}時間復雜度：O(N)
空間復雜度：O(1)
總結：
面對有關陣列的題目，我們通常可以使用幾個常見方法：
1.空間換時間 ：開辟一個與原陣列一樣大小的空間
2.時間換空間：直接遍歷陣列進行操作
3.使用兩個變數，通過下標，操作陣列，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/295219.html
標籤：其他