刪除有序數(shù)組中的重復項
題目入口
題目內(nèi)容
給你一個 非嚴格遞增排列 的數(shù)組 nums ，請你 原地 刪除重復出現(xiàn)的元素，使每個元素 只出現(xiàn)一次 ，返回刪除后數(shù)組的新長度。元素的 相對順序 應該保持 一致 。然后返回 nums 中唯一元素的個數(shù)。
考慮 nums 的唯一元素的數(shù)量為 k ，你需要做以下事情確保你的題解可以被通過：
更改數(shù)組 nums ，使 nums 的前 k 個元素包含唯一元素，并按照它們最初在 nums 中出現(xiàn)的順序排列。nums 的其余元素與 nums 的大小不重要。
返回 k 。
節(jié)選部分內(nèi)容,建議看原題
思路
這種思路我之前也講過講過類似的雙指針問題,這里指針不是真指針,而是表示數(shù)組下標的一種形象的說法
一般來說,我們要先分成兩個數(shù)組模擬來思考思路的,但是本題要是先分兩個數(shù)組來考慮,要用到三指針,所以再試著思考一下下一步的步驟復雜度,下一步我們是要在原數(shù)組進行思考,我們還是設立兩個指針,一個叫big,另一個叫small(本人習慣,big是大哥,small是小弟).
big負責遍歷數(shù)組,不對原數(shù)組進行干涉
small負責修改數(shù)組
不想好一個遍歷的指針在后面判斷跳出循環(huán)容易搞混的
過程就是在big指針遍歷的過程中,判斷small與big各自指向的元素是否相同,因為我們要找不重復的元素,所以當small和big指向的元素不相同的時候,我們要先++small,因為你不加加,small最開始指向的是第一個元素會被覆蓋,所以要先++small覆蓋數(shù)組第二個位置(原題的nums[1])
代碼
big指針用來遍歷,在代碼中初始值應該是0,但是因為small和big都是第一個位置肯定相等,big++為1,這里就直接上來賦值1,也可以在思路上從第二個位置考慮,都行,這里提醒一下
c版本
int removeDuplicates(int* nums, int numsSize)
{
int big = 1;
int small = 0;
while(big<numsSize)
{
if(nums[big]!=nums[small])
nums[++small] = nums[big];
big++;
}
return small+1;
}
c嘎嘎版本
class Solution {
public:
int removeDuplicates(vector<int>& nums)
{
int big = 1;
int small = 0;
while(big<nums.size())
{
if(nums[big]!=nums[small])
{
nums[++small] = nums[big];
}
big++;
}
return small+1;
}
};
合并兩個有序數(shù)組
題目鏈接
題目內(nèi)容
給你兩個按 非遞減順序 排列的整數(shù)數(shù)組 nums1 和 nums2，另有兩個整數(shù) m 和 n ，分別表示 nums1 和 nums2 中的元素數(shù)目。
請你 合并 nums2 到 nums1 中，使合并后的數(shù)組同樣按 非遞減順序 排列。
注意：最終，合并后數(shù)組不應由函數(shù)返回，而是存儲在數(shù)組 nums1 中。為了應對這種情況，nums1 的初始長度為 m + n，其中前 m 個元素表示應合并的元素，后 n 個元素為 0 ，應忽略。nums2 的長度為 n 。
思路
最終排序的有序數(shù)組要在nums1中進行,本題我們采用從后往前的對兩個數(shù)組進行遍歷挑選,采用從前往后的思路是要挪動數(shù)據(jù)的,時間復雜度就上來了,而且麻煩,所有我們不妨換種思路,從后往前來考慮
我們從后往前考慮要注意對兩個數(shù)組邊界進行考慮,無非是nums1數(shù)組有效元素遍歷完或者nums2有效元素遍歷完
第一種情況:nums1有效元素遍歷完,nums2仍然有剩余元素,所以我們繼續(xù)從后往前在nums1數(shù)組進行覆蓋即可
第一個數(shù)組指向的動態(tài)下標我們叫end1,第二個叫end2,在end1后面是我們處理過的元素,end1前面是未處理的元素,又因為本身數(shù)組的有序,所以在我們遍歷完后,即便end2的數(shù)據(jù)覆蓋完,end1沒走到0位置,也是非遞減排序
第二種情況:nums2遍歷完,我剛才說過兩個數(shù)組都是有序數(shù)組,所以在nums2遍歷之后nums1已經(jīng)是非遞減狀態(tài),可以自己嘗試畫圖看一下
代碼
c版本(c嘎嘎版本與c版本內(nèi)容一樣)
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
int end1 = m-1;
int end2 = n-1;
int num = m+n-1;
while(end1>=0&&end2>=0)
{
if(nums2[end2]>nums1[end1])
{
nums1[num] = nums2[end2];
num--;
end2--;
}
else
{
nums1[num] = nums1[end1];
num--;
end1--;
}
}
while(end2>=0)
{
nums1[num] = nums2[end2];
num--;
end2--;
}
}
移除鏈表元素
題目鏈接
題目內(nèi)容
給你一個鏈表的頭節(jié)點 head 和一個整數(shù) val ，請你刪除鏈表中所有滿足 Node.val == val 的節(jié)點，并返回 新的頭節(jié)點 。
思路1
第一種思路就是最直接的思路刪除,而單鏈表的刪除要記得站在本節(jié)點的上一個才能對本節(jié)點進行刪除,所以我們要處理兩個問題,第一個要在針對節(jié)點時分情況討論頭節(jié)點和其他節(jié)點的問題,第二個我前面提過要站在節(jié)點前面才能對本節(jié)點進行修改所以我們要使用兩個動態(tài)指針來標記前一個節(jié)點和該節(jié)點
代碼1
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* big=head,*small=NULL;
//big還是本人習慣的方式,大哥指針,用來
//遍歷鏈表,small就是小弟指針,用來記錄前一個
//節(jié)點的地址
while(big)
{
//第一層判斷就是判斷big指針里的數(shù)值
//是不是所要刪除的數(shù)值
//如果是的就進行刪除操作
//不是的話就跳進下一個
if(big->val==val)
{
//第二層循環(huán)判斷頭節(jié)點等于刪除數(shù)值的情況
//如果是頭節(jié)點是刪除數(shù)值會直接跳入這個
//循環(huán),不會讓small小弟指針記錄
//當然,頭節(jié)點也沒有前節(jié)點,所以就要
//特殊考慮
if(small==NULL)
{
//head頭節(jié)點是刪除數(shù)據(jù)的情況下
//你還要更新頭節(jié)點,讓頭節(jié)點
//指向下一個節(jié)點
//此處可以解決一直出現(xiàn)刪除數(shù)據(jù)的
//情況,比如你要刪除1,然后數(shù)據(jù)給的
//是1 1 1 2,這個代碼可以一直把頭節(jié)點
//更新到第一個頭節(jié)點非刪除值得情況
big = head->next;
free(head);
head=big;
}
else
{
//刪除操作
small->next = big->next;
free(big);
big=small->next;
}
}
else
{
small=big;
big=big->next;
}
}
return head;
}
思路2
鏈表刪除
使用tail指針來遍歷鏈表
tail判斷是不是刪除的對應數(shù)值,如果是就跳過,如果不是就把next指針指向他,并跳到下一個節(jié)點
newnode作為新鏈表(刪除后的鏈表)
newnode賦值的是head的地址,剛開始newnode指向的就是原鏈表,為了方便理解,所以我把在錄視頻的時候分成兩個部分來更好的理解這個思路文章來源：http://www.zghlxwxcb.cn/news/detail-765407.html
代碼2
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* newnode=NULL,* tail=NULL;
while(head!=NULL)
{
if(head->val==val)
{
/*
當節(jié)點指向的是被刪除的對象時,就要跳過這個節(jié)點,指向下一個節(jié)點來達到刪除的目的
*/
head=head->next;
}
else
{
/*
在鏈表不是空鏈表時,對newnode初始化,指向原鏈表
*/
if(newnode==NULL)
{
newnode=head;
tail=newnode;
}
else
{
/*
在head指向不是刪除元素的時候,
用tail進行連接該節(jié)點,并跳到下一個
節(jié)點
*/
tail->next=head;
tail=tail->next;
}
/*
head指向下一個節(jié)點
tail的next指針要置為空,因為這個思路是讓newnode指向新鏈表新的頭節(jié)點,利用tail不斷向后遍歷鏈表來連接非刪除值得節(jié)點,而你tail最后一個不置為NULL,那么在調(diào)用該函數(shù)得時候,無法判斷該鏈表的結(jié)束節(jié)點,tail->next最后一次變成野指針
*/
head=head->next;
tail->next=NULL;
}
}
head=newnode;
return head;
}
思路3
第三種思路與第一種思路類似,是先對頭節(jié)點的情況來討論,然后讓頭節(jié)點是一個非刪除值的節(jié)點,然后進行正常的刪除操作文章來源地址http://www.zghlxwxcb.cn/news/detail-765407.html
代碼3
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val)
{
//判斷是不是空鏈表
if(head==NULL) return head;
//非空鏈表解決一連串的刪除值頭節(jié)點的情況
while(head->next!=NULL&&head->val==val)
{
head=head->next;
}
//看看在刪除完一連串刪除值頭節(jié)點的情況下,
//是否是空鏈表
if(head->next==NULL&&head->val==val)
return NULL;
//頭節(jié)點非刪除值的節(jié)點,開始正常的刪除操作
struct ListNode* p = head;
while(p->next)
{
if(p->next->val==val)
{
struct ListNode* tem = p->next;
p->next = tem->next;
free(tem);
}
else
{
p = p->next;
}
}
return head;
}
到了這里，關于圖靈日記之Leetcode刪除有序數(shù)組中的重復項&&合并兩個有序數(shù)組&&移除鏈表元素的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
