当前位置：首页 > news >正文

代码随想录算法训练 Day1：数组

news 2025/5/15 14:32:38

题目一：

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4       
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2     
输出: -1        
解释: 2 不存在 nums 中因此返回 -1

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

题目二：

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

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

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

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。

示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

你不需要考虑数组中超出新长度后面的元素。

答案：

/*** 数组算法实现类* 包含二分查找和移除元素的不同实现方法*/
public class Array {/*** 二分查找方法一：左闭右闭区间实现 [left, right]* * @param nums 有序数组* @param target 目标值* @return 目标值在数组中的索引，如果不存在则返回-1*/public static int BinarySearch1(int[] nums, int target) {// 左闭右闭二分法 [left, right]int length = nums.length;int left = 0;                  // 查找区间左边界int right = length - 1;        // 查找区间右边界// 当left <= right时，区间[left, right]有效while (left <= right) {int mid = (left + right) / 2;  // 计算中间位置if (nums[mid] == target) {return mid;                 // 找到目标值，返回索引} else if (nums[mid] < target) {left = mid + 1;            // 目标在右半部分，缩小左边界} else {right = mid - 1;           // 目标在左半部分，缩小右边界}}return -1;  // 未找到目标值}/*** 二分查找方法二：左闭右开区间实现 [left, right)* * @param nums 有序数组* @param target 目标值* @return 目标值在数组中的索引，如果不存在则返回-1*/public static int BinarySearch2(int[] nums, int target) {// 左闭右开二分法 [left, right)int length = nums.length;int left = 0;              // 查找区间左边界int right = length;        // 查找区间右边界（注意这里是length而非length-1）// 当left < right时，区间[left, right)有效while (left < right) {int mid = (left + right) / 2;  // 计算中间位置if (nums[mid] == target) {return mid;                 // 找到目标值，返回索引}if (nums[mid] < target) {left = mid + 1;            // 目标在右半部分，缩小左边界} else {right = mid;               // 目标在左半部分，缩小右边界（注意这里是mid而非mid-1）}   }return -1;  // 未找到目标值}/*** 移除元素方法一：暴力解法* 时间复杂度：O(n²)，空间复杂度：O(1)* * @param nums 数组* @param target 要移除的目标值* @return 移除元素后数组的新长度*/public static int RemoveElement1(int[] nums, int target) {// 暴力解法：遍历数组，发现目标元素后，将后面的所有元素前移一位int length = nums.length;for (int i = 0; i < length; i++) {// 找到目标元素if (nums[i] == target) {// 将后面的元素都前移一位for (int j = i; j < length - 1; j++) {nums[j] = nums[j + 1];}i--;        // 下标回退，因为当前位置的元素已被后面的元素替换，需要重新检查length--;   // 数组有效长度减1}}return length;  // 返回新数组的长度}/*** 移除元素方法二：双指针法* 时间复杂度：O(n)，空间复杂度：O(1)* * @param nums 数组* @param target 要移除的目标值* @return 移除元素后数组的新长度*/public static int RemoveElement2(int[] nums, int target) {// 双指针法：快指针遍历数组，慢指针指向新数组的当前位置int length = nums.length;int slow = 0;    // 慢指针，指向新数组下一个要填充的位置// 快指针遍历整个数组for (int fast = 0; fast < length; fast++) {// 当前元素不是目标值时，将其放入slow位置if (nums[fast] != target) {nums[slow] = nums[fast];slow++;   // 慢指针前进}// 当前元素是目标值时，快指针前进，慢指针不动，相当于跳过了这个元素}return slow;  // 返回新数组的长度}/*** 主方法，用于测试*/public static void main(String[] args) {// 测试二分查找int[] num1 = {-1, 0, 3, 5, 9, 12};int target1 = 6;int ans = BinarySearch2(num1, target1);System.out.println("二分查找结果索引: " + ans);// 测试移除元素int[] num2 = {0, 1, 2, 2, 3, 0, 4, 2};int target2 = 2;int ans2 = RemoveElement2(num2, target2);System.out.println("移除元素后的数组长度: " + ans2);// 打印移除元素后的数组内容System.out.print("移除元素后的数组: ");for (int i = 0; i < ans2; i++) {System.out.print(num2[i] + " ");}}
}