题目:给你一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,并返回移除后数组的新长度。 不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
我们的思路还是双指针,定义两个下标fast和slow,从0开始遍历,slow记录数组的长度,fast找到不为val的值,就把值赋给slow,然后slow的长度+1,直到fast>numsSize;
int removeElement(int* nums, int numsSize, int val)
{
int fast = 0;
int slow = 0;
while (fast < numsSize)
{
//当fast下标对应的元素不等于要删除的值,将fast的值赋给slow
if (nums[fast] != val)
{
nums[slow] = nums[fast];
slow++;
fast++;
}
//否则,说明slow到fast的值都是val的值,fast继续往后走
else
{
fast++;
}
}
return slow;
}
题目:给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
方法一、循环法
int searchInsert(int* nums, int numsSize, int target)
{
int i = 0;
//从头遍历,如果找到target就返回i
for (i = 0; i < numsSize; i++)
{
if (nums[i] == target)
return i;
}
//判断target是否大于最后一个元素,若大于,返回i
if (nums[i - 1] < target)
return i;
//前两种情况都不是,则应该就是需要将target插入数组中;
//我们只需要找到第一个比target大的数,返回它的下标即可;
for (i = 0; i < numsSize; i++)
{
if (nums[i] > target)
break;
}
return i;
}
方法二、二分查找法
int searchInsert(int* nums, int numsSize, int target)
{
//定义left从头开始和right从尾开始
int left = 0;
int right = numsSize - 1;
//当left小于等于right时循环继续
while (left <= right)
{
//定义left和right的二分值mid
//使用left + (right - left) / 2,是为了防止溢出
int mid = left + (right - left) / 2;
if (nums[mid] == target)
return mid;
else if (nums[mid] > target)
right = mid - 1;
else if (nums[mid] < target)
left = mid + 1;
}
//当需要插入的时候,left和right总会重合,那么nums[mid]的值总会小于target
//所以就会执行left = mid + 1,left就会大于right,
//mid+1就是需要插入的下标,也就是left,所以返回left
return left;
}