首页 > 代码库 > leetcode(二)

leetcode(二)

2024-09-08 04:30:53   209人阅读

Remove Duplicates from Sorted Array

Given a sorted array, 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 in place with constant memory.

For example, Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

题目要求是不能申请额外的空间，返回修改后的数组长度，大概代码如下：

//STL标注模板库函数unique(),删除相邻的相同的元素；
int removeDuplicates(vector<int>& nums) {
    return distance(nums.begin(), unique(nums.begin(), nums.end()));
}

//不使用标准模板库函数
顺序循环判断
int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) return 0;

    int count = 0;    //返回长度
    for (int i = 1; i < nums.size(); i++) {
        if (nums[count] != nums[i]) {    //相邻元素不相同，判断下两个        
            nums[++count] = nums[i];
        }
    }
　　 return count + 1;
}

Remove Duplicates from Sorted Array II

Follow up for ”Remove Duplicates”: What if duplicates are allowed at most twice?
For example, Given sorted array A = [1,1,1,2,2,3],
Your function should return length = 5, and A is now [1,1,2,2,3]

每个元素最多不能超过两次，返回数组的长度。

int removeDuplicates(vector<int>& nums) {
    if (nums.size() <= 2) return nums.size();

    int count = 2;    //至少长度为2
    for (int i = 2; i < nums.size(); i++) {
        if (nums[i] != nums[count - 2]) {    //相邻第二个是否相同
            nums[++count] = nums[i];
        }
    }
    return count;
}

Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.

前提是已经排序的数组经过其中某个值翻转，分为两部分相同的值。二分查找即可：

int binSearch(vector<int> nums, int target) {
    int first = 0, last = nums.size();
    while (first != last) {
        int mid = first + (first + last) / 2;

        if (nums[mid] = target)        //target恰好在中间。
            return mid;

        if (nums[first] <= nums[mid]) {
            if (nums[first] < target && target < nums[mid])  //前半部分
                last = mid;
            else 
                first = mid + 1;
        }
        else {
            if (nums[mid] < target && target < nums[last]) {    //后半部分
                first = mid + 1;
            }
            else
                last = mid + 1;
        }
    }
}

 

leetcode(二)


联系
我们