广州网站建设骏域,网站建设怎么配置伪静态文件,wordpress评论不了,企业管理专业大学排名目录
1.合并两个有序数组
2.移动元素 3.删除有序数组中的重复项 4.删除排序数组中的重复项 II
5.多数元素
暂时更新到这里#xff0c;博主会持续更新的 1.合并两个有序数组
题目#xff08;难度#xff1a;简单#xff09;#xff1a;
给你两个按 非递减顺序 排列的…目录
1.合并两个有序数组
2.移动元素 3.删除有序数组中的重复项 4.删除排序数组中的重复项 II
5.多数元素
暂时更新到这里博主会持续更新的 1.合并两个有序数组
题目难度简单
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2另有两个整数 m 和 n 分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中使合并后的数组同样按 非递减顺序 排列。
注意最终合并后数组不应由函数返回而是存储在数组 nums1 中。为了应对这种情况nums1 的初始长度为 m n其中前 m 个元素表示应合并的元素后 n 个元素为 0 应忽略。nums2 的长度为 n 。 解法一
思路先合并两个数组然后通过冒泡排序进行排序
public void merge(int[] nums1, int m, int[] nums2, int n) { // 获取nums1数组的长度 int length1 nums1.length; // 从nums1的有效元素末尾开始将nums2的所有元素复制到nums1的剩余空间 for (int i m; i length1; i) { nums1[i] nums2[i - m]; } // 从nums1的开头开始进行冒泡排序以确保整个nums1数组是有序的 for (int i 0; i length1 - 1; i) { if (nums1[i] nums1[i 1]) { // 如果当前元素大于其相邻的元素则交换它们 int tmp nums1[i]; nums1[i] nums1[i 1]; nums1[i 1] tmp; } } }
解法二
思路数组nums1和nums2通过比较的方式填充nums1末尾 public void merge(int[] nums1, int m, int[] nums2, int n) { // 初始化指向nums1和nums2末尾的指针 int i m - 1; // nums1中有效数据的最后一个索引 int j n - 1; // nums2中有效数据的最后一个索引 // 初始化指向nums1最终位置的指针 int k nums1.length - 1; // nums1的末尾索引也是合并后数组的末尾索引 // 当nums2中还有元素未处理时执行循环 while (j 0) { // 如果nums1中还有元素并且当前nums1元素大于nums2元素 if (i 0 nums1[i] nums2[j]) { // 将nums1当前元素放到最终位置并将指针向前移动 nums1[k--] nums1[i--]; } else { // 否则将nums2当前元素放到nums1的最终位置并将指针向前移动 nums1[k--] nums2[j--]; } } // 循环结束后nums1包含了合并后的有序数组
}
2.移动元素
题目难度简单 给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素并返回移除后数组的新长度。
不要使用额外的数组空间你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 解法一
public int removeElement(int[] nums, int val) { int length 0; // 用于记录非目标值元素的数量也即新数组的长度 for (int i 0; i nums.length; i) { // 如果当前元素不等于目标值val if (nums[i] ! val) { // 将该元素移动到数组的前端覆盖length位置上的元素 nums[length] nums[i]; // 更新非目标值元素的数量 length; } // 如果当前元素等于目标值val则不做任何操作直接跳过 } // 返回新数组的长度 return length;
} 解法二
public int removeElement(int[] nums, int val) { // 初始化右指针j为数组末尾的索引 int j nums.length - 1; // 遍历数组左指针i从数组开始位置到j之前的位置 for (int i 0; i j; i) { // 如果当前元素等于目标值val if (nums[i] val) { // 交换当前元素nums[i]与右指针指向的元素nums[j] int tmp nums[i]; nums[i] nums[j]; nums[j] tmp; // 由于已经交换了一个等于val的元素到数组末尾所以j向左移动一位 j--; // 由于交换后当前位置的元素可能又变成了需要移除的值所以i也需要向左移动一位 i--; } } // 返回j1作为新数组的长度因为j此时指向最后一个有效元素的下一个位置 return j 1;
} 3.删除有序数组中的重复项
题目难度简单
给你一个 非严格递增排列 的数组 nums 请你 原地 删除重复出现的元素使每个元素 只出现一次 返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k 你需要做以下事情确保你的题解可以被通过
更改数组 nums 使 nums 的前 k 个元素包含唯一元素并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。返回 k 。 解法一
public int removeDuplicates(int[] nums) { // 使用双指针p和qp指向当前不重复序列的末尾q用于遍历数组 int p 0; int q 1; // 当q指针未到达数组末尾时执行循环 while (q nums.length) { // 如果当前p和q指向的元素不相等说明找到了一个新的不重复元素 if (nums[p] ! nums[q]) { // 如果q和p之间的元素个数大于1说明有多个重复元素 // 此时将q指向的元素复制到p的下一个位置覆盖掉多余的重复元素 if (q - p 1) { nums[p 1] nums[q]; } // p指针前移一位指向新的不重复序列的末尾 p; } // q指针前移一位继续遍历数组 q; } // 返回新的数组长度即p1因为p指向的是最后一个不重复元素的下一个位置 return p 1;
} 4.删除排序数组中的重复项 II
题目难度中等
给你一个有序数组 nums 请你 原地 删除重复出现的元素使得出现次数超过两次的元素只出现两次 返回删除后数组的新长度。
不要使用额外的数组空间你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 解法一
public int removeDuplicates(int[] nums) { // 获取数组的长度 int length nums.length; // 初始化指针p和q // p指向新数组的最后一个已处理元素之后的位置 // q从数组的第三个元素开始遍历索引为2 int p 0; int q 2; // 当q指针还没有遍历完整个数组时继续执行循环 while (q length) { // 如果p指针指向的元素与q指针指向的元素不同 // 说明找到了一个新的、不重复的元素 if (nums[p] ! nums[q]) { // 将这个新元素复制到p指针之后的位置 // 因为p指针指向的是新数组的最后一个已处理元素之后的位置 // 所以新元素应该放在p2的位置因为p1的位置是留给下一个不重复元素的 nums[p 2] nums[q]; // 将p指针前移一位为下一个不重复元素腾出空间 p; } // q指针无论如何都前移一位继续遍历数组 q; } // 返回新数组的长度 // 由于数组索引是从0开始的所以新数组的长度是p2 // 其中p是新数组的最后一个已处理元素的位置所以p2是新数组的长度 return p 2;
}
5.多数元素
题目难度简单
给定一个大小为 n 的数组 nums 返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的并且给定的数组总是存在多数元素。
解法一
public int majorityElement(int[] nums) { // 初始化候选元素和计数器 int candidate nums[0]; // 将候选元素初始化为数组的第一个元素 int count 0; // 计数器 // 遍历数组 for (int num : nums) { // 如果计数器为0则当前元素为候选元素并将计数器设为1 if (count 0) { candidate num; count 1; } // 如果当前元素与候选元素相同则计数器加1 else if (num candidate) { count; } // 如果当前元素与候选元素不同则计数器减1 else { count--; } } // 返回候选元素即为多数元素 return candidate; } 暂时更新到这里博主会持续更新的
