OJ每日练习（1）

Posted on | In

题目名称

  1. Remove Duplicates from Sorted Array（Leetcode #26)
  2. Remove Duplicates from Sorted ArrayⅡ ( Leetcode #80)
  3. 数组中重复的数字（剑指offer #3）

Remove Duplicates from Sorted Array（Leetcode #26)

题目描述

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

解题思路

数组的常规删除操作需要耗费线性时间，显然效率过低，考虑到有序数组的特殊性，我们只需要遍历数组，将每一个不同前一个元素的元素置于新数组对应位置即可。

解题方案

方案一：直接使用STL

1
2
3
4
5
6
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        return distance(nums.begin(),unqiue(nums.begin(),nums.end()));  
    }
};

方案二:手动实现

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size()==0 || nums.size()==1)
            return nums.size();
        size_t newsize=1;
        for(size_t index=1;index!=nums.size();++index)
            if(nums[index]!=nums[index-1])
                nums[newsize++]=nums[index];
        return newsize;
    }
};

Remove Duplicates from Sorted ArrayⅡ ( Leetcode #80)

题目描述

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most k times and return the new length.Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

解题思路

本题是上一题的变体，其要点在于当前数组内允许元素至多重复k次。解题思路十分明了：在上一题中我们采用的是每一个元素与前一个元素比较的策略，本题则改为：首先将nums[k]与nums[0]相比较,如果不相同,更新数组大小与被比对象，相同则不执行更新。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int removeDuplicates(vector<int>& nums,size_t k) {
        if(nums.size()<=k)
            return nums.size();
        size_t newsize=k;
        size_t compareIndex = 0;
        for(size_t index=k;index!=nums.size();++index)
            if(nums[index]!=nums[compareIndex])
                nums[newsize++]=nums[index],++compareIndex;
        return newsize;
    }
};

数组中重复的数字（剑指offer #3)

题目描述

在一个长度为n的数组中存储着值分布在[0,n)区间的元素，试找出某个重复元素。

解题思路

由于值的区间已知且线性正比于规模，使用数组存储元素出现的次数是一种十分显然的解法，但其空间成本太高。我们只需要找出元素是否重复，并不需要了解其重复次数，因此可将原有数组改造，令下标与值一一对应，若某个值出现在多个下标对应的内存位置上，则该值重复。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        for(size_t index =0;index!=nums.size();++index){
            while(nums[index]!=index){
                if(nums[index]==nums[nums[index]])
                    return nums[index];
                else
                    swap(nums[index],nums[nums[index]]);
            }
        }
        return -1;
    }
};

进阶

若当前数组长度为n，数值区间为[1,n）,试以不破坏原始数组的就地算法找出某一个重复元素。

解题思路

分治策略：设m为区间[1,n）中间数，若[1，m]在数组中出现的次数大于m，则[1，m]中必然存在重复元素，再次执行分治求解。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        size_t low = 1;
        size_t high = nums.size()-1;
        while(low<high){
            size_t mid = low+(high-low)/2;
            size_t count = 0;
            for(auto i:nums)
                if(i<=mid) ++count;
            if(count<=mid)
                low = mid+1;
            else
                high=mid;
        }
        return low;
    }
};