【20190306】【每天一道算法題】移除元素

問題：

給定一個數組 nums 和一個值 val，你需要原地移除所有數值等于 val 的元素，傳回移除後數組的新長度。

不要使用額外的數組空間，你必須在原地修改輸入數組并在使用 O(1) 額外空間的條件下完成。

元素的順序可以改變。你不需要考慮數組中超出新長度後面的元素。

首先談下我的看法：

我的思路是，對于 val=2 ，而 nums[8]={0,1,2,2,3,0,4,2} 這樣的情況，我們可以逐個檢查 nums[i] ，如果 nums[i]==val ，那麼将最後一位元素指派給目前的 nums[i]（就實作了删除目前等于 val 的這個元素，但注意同時不要跳過目前的 i ，要再一次進行檢查！）

這樣就存在一個問題，對于 val=3 ，而 nums[2]={3,3} 的情況（即所有元素都要删除的情況），這種想法實作不了！！！

/*按照我的思路編寫的程式*/
#include<stdio.h>
#include<stdlib.h>

int removeElement(int* nums, int numsSize, int val);

void main()
{
	int result;
	int nums[8]={0,1,2,2,3,0,4,2};
	result=removeElement(nums,8,2);

	printf("%d\n",result);
	//printf("%d",nums);   //這樣無法正确輸出數組！因為字元型數組可以一次性輸出，但數值型數組需要循環輸出！

	system("pause");
}

int removeElement(int* nums, int numsSize, int val)
{
    int *p=nums;
	int i,j;
	//for(;p!='\0';p++)
	for(i=0;i<numsSize;i++)
	{
		if(*p==val)
		{
			*p=nums[numsSize-1];
			numsSize--;
			
		}
		else
		{
			p++;   //隻有當*p!=val時，p才加一，即向後移一位！
		}
	}
	return numsSize;
}
           

官方思路

1. 雙指針

定義兩個指針 i（慢指針）和 j（快指針），當 nums[j] 與 val 相等時，遞增 j 以跳過該元素，隻要 nums[j]!=val ，我們将 nums[j] 複制給 nums[i] ，同時遞增兩個索引，重複這個過程，直到 j 到達數組的末尾，該數組的新長度為 i 。

複雜度分析：

1. 時間複雜度：O(n) ，假設數組共有 n 個元素， i 和 j 至少周遊 2n 步。

2. 空間複雜度：O(1)（因為是“就地”、“原地”）。

2. 雙指針——當要删除的元素很少時

就可以用我的思路，将目前元素與最後一個元素進行交換，并釋放最後一個元素，注意：被交換的最後一個元素也可能是想要移除的值，是以對其要進行再一次檢查！

複雜度分析：

1. 時間複雜度：O(n) ，i 和 j 最多周遊 n 步，這種方法中，指派操作的次數等于要删除元素的個數。是以，如果要移除的元素很少時，該方法效率更高。

2. 空間複雜度：O(1)（因為是“就地”、“原地”）。

解答：

#include<stdio.h>
#include<stdlib.h>

int removeElement(int* nums, int numsSize, int val);

void main()
{
	int nums[2]={3,3};
	int result;
	result=removeElement(nums,2,3);

	printf("%d\n",result);
	//printf("%d",nums);  // 如何輸出數組

	system("pause");
}

int removeElement(int* nums, int numsSize, int val)  //用指針（效率更高，即所用時間短）
{
	int *i=nums,*j=nums;
	int n,m=0;
	for(n=0;n<numsSize;n++)   //n用來計循環次數
	{
		if(*j!=val)
		{
			*i=*j;
			i++;
			m++;   //m用來表示最終數組有幾位
		}
		j++;
	}
	return m;
}

//int removeElement(int* nums, int numsSize, int val)  //用數組
//{
//	int i=0,j=0;
//	for(;j<numsSize;)
//	{
//		if(nums[j]!=val)
//		{
//			nums[i]=nums[j];
//			i++;
//		}
//		j++;
//	}
//	return i;
//}
           

知識點：

1. 注釋：Ctrl+K+C；

2. 取消注釋：Ctrl+K+U；

3. 編譯錯誤：【找到一個或多個多重定義的符号】它說你定義了兩個main，你得工程中有“源.cpp"和“源2.cpp”，在一個工程中，不允許有兩個源檔案分别定義main，需要删除一個。（即，不能在同一個工程裡面定義兩個main函數！）

同類型題目：

删除排序數組中的重複項