leetcode26:删除排序數組中的重複項

• 題目描述
• • 第一種解題思路：
  • 第二種解決思路：
  • 第三種解決思路：

題目描述

第一種解題思路：

因為數組是已經排好序的有序數組，是以後面的元素一定是大于等于前面的數字的，是以我們隻需要判斷後一個數字是否與前一個數字相等，如果相等就讓後一個繼續向後，直到不等于目前數為止，如果不相等就讓前面的下标向後移動一位指派，最後的長度就是前面下标+1

/*
 * LeetCode, Remove Duplicates from Sorted Array
 * 時間複雜度O(n)，空間複雜度O(1)
 */
class Solution {
public:
    int removeDuplicates( vector<int> & nums )
    {
        if ( nums.empty() )
            return(0);
        int index = 0;
        for ( int i = 1; i < nums.size(); i++ )
        {
            if ( nums[index] != nums[i] )
                nums[++index] = nums[i];
        }
        return(index + 1);
    }
};
           

• 判斷一個矢量是否為空，使用empty（）函數最好，不要使用0 == v.size（）

• if ( nums[index] != nums[i] )

  nums[++index] = nums[i];

• 上邊代碼的方式可以适用于有序array前移的操作

第二種解決思路：

利用STL中的distance以及unique接口：

distance有兩個參數為疊代器，計算兩個疊代器之間的距離；

unique()傳回不重複重排array的尾後繼承器

distance介紹

unique的兩個參數也為疊代器，它保證了相鄰的資料之間沒有重複項，例如：{ 1, 2, 2, 3, 3, 3, 2, 4, 4}的結果就是{1, 2, 3, 2, 4}；可以發現其中仍然是存在重複項的，因為unique隻保證相鄰的兩個資料是唯一的，在本題中不會出現這個問題，因為題中的數組為有序的。傳回值也是一個疊代器，表示相鄰的不重複項的最後一個位址。

unique介紹

// 代碼實作簡單，但是需要對接口熟悉
// 接口在頭檔案 #include <algorithm>中
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
       return distance(nums.begin(), unique(nums.begin(), nums.end()));
    }
};
           

第三種解決思路：

同樣用到了STL中的接口upper_bound

upper_bound需要在排序數組中使用

在從小到大的數組中，upper_bound的作用是利用二分查找，找到第一個大于val的值，直到找到 last位置

upper_bound介紹

// 頭檔案#include <algorithm>
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
       return removeDuplicates(nums.begin(), nums.end(), nums.begin()) - nums.begin();
    }
    template<class InIt, class OutIt>//相當于對unique的一種實作方式
    OutIt removeDuplicates(InIt first, InIt last, OutIt output)
    {
        while(first != last)
        {
            *output++ = *first;
            first = upper_bound(first, last, *first);
        }
        return output;
    }
    
};
           

• upper_bound(first, last, first)傳回指向第一個比first大的元素的繼承器，其中，first，last都是疊代器。
• 使用了函數模闆，調用時生成對應的執行個體，InIt執行個體化為繼承器類型vector::iterator，OutIt也執行個體化為vector::iterator。
• 前置++解與引用級别一樣，右結合律，後置++級别比高1級，右結合律
• distance()傳回首尾之間的元素數，左閉右開
• 傳回的output，就是重排最後一個元素之後的一個疊代器