LeetCode 704.二分查找
题目描述
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
题目链接
解题思路
根据二分查找的特性，双指针查找
// 耗时：4m40s
class Solution {
public int search(int[] nums, int target) {
int start = 0, end = nums.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (target > nums[mid]) {
start = mid + 1;
} else if (target < nums[mid]) {
end = mid - 1;
} else {
return mid;
}
}
return -1;
}
}
LeetCode 27.移除元素
题目描述
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
- 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
- 返回 k。
示例
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,,]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。
题目链接
解题思路
双指针，快指针用来搜索，慢指针用来指定新数组下标。
// 耗时：5m03s
class Solution {
public int removeElement(int[] nums, int val) {
int left = 0, right = 0;
while (right < nums.length) {
if (nums[right] != val) {
nums[left++] = nums[right];
}
right++;
}
return left;
}
}
LeetCode 977.有序数组的平方
题目描述
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
题目链接
解题思路
双指针，最大的平方，不是最左边就是最右边。从大往小插入排序
// 耗时: 2m49s
class Solution {
public int[] sortedSquares(int[] nums) {
int left = 0, right = nums.length - 1;
int[] ans = new int[nums.length];
for (int i = nums.length - 1; i >= 0; i--) {
int a = nums[left] * nums[left];
int b = nums[right] * nums[right];
if (a < b) {
ans[i] = b;
right--;
} else {
ans[i] = a;
left++;
}
}
return ans;
}
}
评论