标签归档:线性表

LeetCode:Search in Rotated Sorted Array II

接前一题(Search in Rotated Sorted Array),但数组中的元素允许重复。
LeetCode OJ地址:http://oj.leetcode.com/problems/search-in-rotated-sorted-array-ii/
关键点:旋转前数组有序,可能有重复元素。


我的解法:
前一题能利用折半查找思想的关键是旋转后数组分为两个有序子区间,可以通过A[first]A[mid]A[last-1]target的大小测试来快速缩小查找范围。由于本题中数组可能有重复元素,如对于数组[1,3,1,1,1]A[first]=A[mid]=A[last-1]=1,此时将无法确定是应该将查找区间搜小到A[first,mid)还是A[mid+1,last)。
因此,算法加入高亮代码行17和18的判断,当这三个元素相等时,只++first
注:search返回值由位置索引int修改为是否存在标识bool
// 时间复杂度O(n),空间复杂度O(1)
class Solution {

LeetCode:Search in Rotated Sorted Array

Search in Rotated Sorted Array:http://oj.leetcode.com/problems/search-in-rotated-sorted-array/
关键点:旋转前数组有序,无重复元素。


参考解法:
由于旋转前数组有序,故旋转后,数组被分为两个有序的子区间(无旋转时为一个有序区间)。
算法同样采用折半查找的思想进行搜索,但上下界firstlast的更新相比常规的折半查找略微复杂。
在下面的高亮行11进行判断时,若if判断成立,由旋转前数组有序的条件可知firstmid之间的元素都有序(在一个有序子区间中),故在高亮行12时若if仍成立,则target[first,mid)之间,否则在[mid+1,last)之间。
同上述分析,在高亮行18时若if成立,则target[mid+1,last)之间。
// 时间复杂度O(log n),空间复杂度O(1)
class 

LeetCode:Remove Duplicates from Sorted Array II

接前一题(Remove Duplicates from Sorted Array),但元素最多允许出现的次数由1变为2。
LeetCode OJ地址:http://oj.leetcode.com/problems/remove-duplicates-from-sorted-array-ii/
关键点:数组已排序,不分配另一个数组,返回去重后数组长度,每个元素最多出现两次。


我的解法1:
1.遍历数组,将其中重复次数在两次以上的所有元素进行标记(mark,此处使用A[0]-1作为mark,对于A[0]本身为最小int时可能存在问题?)。
2.从第一个重复次数在两次以上且该数第三次出现的位置开始遍历,当元素不是被标记的元素时,将该元素往前移动。
算法需要执行两次循环及一次STL的find操作,虽然时间复杂度在O(n),但实际效果并不好,且代码冗长。
对于一个测试用例,算法在执行过程中的数组状态如下代码中的高亮行所示。
// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int removeDuplicates(int A[], int n) {
        if (0 

LeetCode:Remove Duplicates from Sorted Array

开始尝试刷LeetCode提升下算法功力,打算所有算法先自己尝试编写,再参考Frank Dai(SoulMachine)在GitHub上的题解
Remove Duplicates from Sorted Array:
关键点:数组已排序,不分配另一个数组,返回去重后数组长度,每个元素只出现一次。


我的解法:
算法主要思路为不断前向查找,当找到一个不再重复的元素时,将该元素复制到已经去重的最后一个元素的下一个相邻位置。前向查找及元素复制位置由索引frontback维护。
// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int removeDuplicates(int A[], int n) {
        // 边界测试
        if (0 == n)
            return 0;

        // front 指向当前需要判断是否需要被去重的元素
        //