第一題：移除元素
思路一：
一：暴力查找的方法：
1.找到對應val值的下標，返回數(shù)組的下標。
2.刪除對應的下標，從前向后用后面覆蓋前面。當后一個是數(shù)組最后一個數(shù)值是就賦值結束了（注意數(shù)組越界的問題）。
3.刪除了一個數(shù)之后數(shù)組元素個數(shù)要–。
4.查找和刪除是在一個循環(huán)里面因為val的值可能在數(shù)組中出現(xiàn)多次，直到返回的下標的值沒有了，就結束了循環(huán)，val的數(shù)值都移除完了。
// 順序表查找
int SeqListFind(int* ps, int x,int nume)
{
//遍歷查找
int n = nume;
for (int i = 0; i < n; i++)
{
if (ps[i] == x)
{
return i;
}
}
return -1;
}
// 順序表刪除pos位置的值
void SeqListErase(int* ps, int pos,int num)
{
int n = num;
for (int i = pos; i < n-1; i++)
{
ps[i] = ps[i+1];
}
}
int removeElement(int* nums, int numsSize, int val){
while(1)
{
int b=SeqListFind(nums,val,numsSize);
if(b==-1)
{
break;
}
else
{
SeqListErase(nums,b,numsSize);
numsSize--;
}
}
return numsSize;
}
思路二：
二：使用雙指針的方法
1.不要使用額外的數(shù)組空間，你必須僅使用 O(1) 額外空間并 原地 修改輸入數(shù)組。
2.定義兩個下標：src和dis，他們開始的時候是在一起的對應的數(shù)組值都不是val的時候，同時++。
3.只要src位置是val就src++；
4.當src位置不是val就把src位置的值賦值到dis，到src>n-1循環(huán)結束
int removeElement(int* nums, int numsSize, int val)
{
int src=0;
int dis=0;
int n=numsSize;
int count=0;
while(src<=n-1)
{
if((src==dis) && (nums[src]!=val))
{
src++;
dis++;
}
else if((nums[src]==val))
{
src++;
count++;
}
else if((nums[src]!=val))
{
nums[dis]=nums[src];
src++;
dis++;
}
}
return n-count;
}
第二題：
第二題：
思路一：
一.雙指針的方法
1.定義p1,p2 兩個變量，初始化為0從兩個數(shù)組開頭開始向后移動。
2.同時比較nums1[p1]和nums2[p2]這兩個位置的數(shù)值。
3.開辟一個新的數(shù)組大小為m+n兩個數(shù)組長度的和。
4.在比較的過程中較小的值放到新的數(shù)組，開辟數(shù)組的下標++，小的值的數(shù)組的下標++。
5.結束條件p1>=m 中有一個 p2>=n就結束。
6.出來之后另一個沒有放完，p1=m,說明nums2沒有放完。反之同理。
7.tmp拷貝回去到nums1中
空間復雜度是O（N）時間復雜度O（2*（M+N））；文章來源：http://www.zghlxwxcb.cn/news/detail-609726.html
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
int p1=0;
int p2=0;
int* tmp=(int*)malloc(sizeof(int)*(m+n));
int i=0;
while((p1<m)&&(p2<n))
{
if(nums1[p1]>=nums2[p2])
{
*(tmp+i)=nums2[p2];
p2++;
i++;
continue;
}
else if(nums1[p1]<nums2[p2])
{
*(tmp+i)=nums1[p1];
p1++;
i++;
continue;
}
}
if(p1>m-1)
{
memcpy(tmp+i,nums2+p2,sizeof(int)*(n-p2));
}
else if(p2>n-1)
{
memcpy(tmp+i,nums1+p1,sizeof(int)*(m-p1));
}
memcpy(nums1,tmp,sizeof(int)*(m+n));
}
思路二：
三指針的方法：
1.p1起始位置是m-1，p2起始位置是n-1.數(shù)組值的尾。
2.end起始位置是（m+n）-1在nums1上。
3.分別從尾開始比較賦值到nums1[end]位置，誰賦值過去對應的p就–，end–。
4.當p1==-1,p2還沒有結束需要把值賦值到對應的num1上。
5.當p2==-1就說明已經結束。
時間復雜度優(yōu)化到了O（m+n）文章來源地址http://www.zghlxwxcb.cn/news/detail-609726.html
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
int p1=m-1;
int p2=n-1;
int end=(m+n)-1;
while(p1>=0 && p2>=0)
{
if(nums1[p1]>nums2[p2])
{
nums1[end]=nums1[p1];
p1--;
end--;
}
else
{
nums1[end]=nums2[p2];
p2--;
end--;
}
}
while(p2>=0)
{
nums1[end]=nums2[p2];
p2--;
end--;
}
}
到了這里，關于C語言每日一題：6.移除元素+合并兩個有序數(shù)組。的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
