算法实战(数组篇)

26.删除有序数组中的重复项

题目详情

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。

题解

int removeDuplicates(int* nums, int numsSize) {
    int i=0,count;
    for(int j=1;j<numsSize;j++){
        if(nums[i]!=nums[j])
            nums[++i]=nums[j];
    }
    count=i+1; // i是数组下标,count应该比i多1.
    return count;
}

27. 移除元素

##题目详情
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

题解

int removeElement(int* nums, int numsSize, int val) {
    int count=0; // 记录val值的个数
    for(int i=0;i<numsSize;i++){
        if(nums[i]==val) // 数组的值等于val值,count++
            count++;
        else
             nums[i-count]=nums[i];
    }
    return numsSize-count;
}

35. 搜索插入位置

题目详情

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

题解

int searchInsert(int* nums, int numsSize, int target) {
    int low=0,high=numsSize-1;
    while(low<=high){
        int mid=(low+high)/2;
        if(nums[mid]==target)
            return mid;
        else if(nums[mid]>target)
            high=mid-1;
        else
            low=mid+1;
    }
    return low; // low指向的位置是target元素应该在数组中存放的位置
}

66. 加1

题目详情

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

题解

int* plusOne(int* digits, int digitsSize, int* returnSize) {
   for(int i=digitsSize-1;i>=0;i--){
       if(digits[i]<9){
           digits[i]++;
           (*returnSize)=digitsSize;
           return digits;
       }else{
           digits[i]=0;
       }
   }
   int* res=(int*)malloc(sizeof(int)*(digitsSize+1));
   res[0]=1;
   for(int i=1;i<digitsSize+1;i++)
        res[i]=digits[i-1];
    (*returnSize)=digitsSize+1;
    return res;     
}