704.二分查找、27.移除元素

简介: ### 704. 二分查找题目要求在有序数组中查找目标值,若存在则返回下标,否则返回 -1。通过二分查找实现,时间复杂度为 O(log n)。关键点在于正确计算中间索引 `mid`,并避免溢出。提供了 C++、Java 和 Python 的实现代码。### 27. 移除元素题目要求原地移除数组中所有等于指定值的元素,并返回新数组长度。使用快慢指针法,将不等于目标值的元素移动到数组前部,从而实现 O(1) 空间复杂度的要求。同样提供了 C++、Java 和 Python 的实现代码。两题均注重算法效率与空间优化,适合初学者练习基础算法思想。

题目: 704. 二分查找  

力扣704.二分查找

给定一个 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]之间。

思考历程与知识点:  

       考查二分查找能力,注意mid的取值。

注意:

       右端点的大小,需要在数组长度上-1。也就是nums.size()-1,因为下标是从0开始的。

题解:

c++:
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int mid;
        int i = 0, j = nums.size() - 1;
        while(j >= i) {
         // mid = (i + j + 1)/2; //这个也对,但为了防止溢出选择下面这种写法
            mid = i + ((j - i) / 2);
            if(nums[mid] == target) return mid;
            else if(nums[mid] > target) j = mid - 1;
            else i = mid + 1;
        }
        return -1;
    }
};

其他语言版本:

java
class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid;
        }
        return -1;
    }
}
python:
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)  # 定义target在左闭右开的区间里,即:[left, right)
 
        while left < right:  # 因为left == right的时候,在[left, right)是无效的空间,所以使用 <
            middle = left + (right - left) // 2
 
            if nums[middle] > target:
                right = middle  # target 在左区间,在[left, middle)中
            elif nums[middle] < target:
                left = middle + 1  # target 在右区间,在[middle + 1, right)中
            else:
                return middle  # 数组中找到目标值,直接返回下标
        return -1  # 未找到目标值

题目: 27.移除元素

力扣27.移除元素

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

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

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

说明:

为什么返回数值是整数,但输出的答案是数组呢?

请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说,不对实参作任何拷贝

int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。

// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。

for (int i = 0; i < len; i++) {

   print(nums[i]);

}

示例 1:

输入:nums = [3,2,2,3], val = 3

输出:2, nums = [2,2]

解释:函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如,函数返回的新长度为 2 ,而 nums = [2,2,3,3] 或 nums = [2,2,0,0],也会被视作正确答案。

示例 2:

输入:nums = [0,1,2,2,3,0,4,2], val = 2

输出:5, nums = [0,1,4,0,3]

解释:函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0,1,3,0,4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

思考历程与知识点:  

   第一反应是求有几个val,用总长度减掉就可以了。发现题目要求原地修改数组。

   既然题目说顺序可变,那每当找到一个val,就把它丢到最后面,然后数组长度减1,不就是丢掉了。再把当前最后面那个放回这个val丢完之后的空位,就可以了

注意:

       当 i > j 时就要跳出for,而不是遍历到数组最后一个再跳,因为 j 后面都是我们丢过去的val,不能遍历到他们。

题解:

c++:
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int j = nums.size() - 1;
        for(int i = 0; i <= j; i++) {
            if(nums[i] == val) swap(nums[i--], nums[j--]);;
        }
        return j+1;
    }
};

其他语言版本:

java:
class Solution {
    public int removeElement(int[] nums, int val) {
        // 快慢指针
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != val) {
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;
    }
}
python:
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        # 快慢指针
        fast = 0  # 快指针
        slow = 0  # 慢指针
        size = len(nums)
        while fast < size:  # 不加等于是因为,a = size 时,nums[a] 会越界
            # slow 用来收集不等于 val 的值,如果 fast 对应值不等于 val,则把它与 slow 替换
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        return slow


相关文章
|
3月前
|
SQL 监控 安全
数据同步如何保证不重、不丢、不错?一文讲清全量、增量、校验和异常处理
企业数据同步真正的风险不是任务报错,而是“假成功”——数据重复、遗漏或失真。可靠同步必须回答三个核心问题:是否幂等(不重)、是否全量捕获变化(不丢)、是否保持业务含义准确(不错)。需构建覆盖一致性快照、CDC/时间戳增量、幂等写入、分层校验与分类恢复的可信链路。(239字)
|
机器学习/深度学习 PyTorch 算法框架/工具
高效处理多维数组:einsum()函数从入门到精通
本文深入解析了NumPy中的`einsum()`函数,从基础语法到高级应用全面展开。文章首先介绍了爱因斯坦求和约定的数学基础,解释了`einsum()`如何通过简洁的索引符号实现复杂的多维数组运算。
685 5
高效处理多维数组:einsum()函数从入门到精通
|
存储 SQL Java
Flink CDC + Hologres高性能数据同步优化实践
本文整理自阿里云高级技术专家胡一博老师在Flink Forward Asia 2024数据集成(二)专场的分享,主要内容包括:1. Hologres介绍:实时数据仓库,支持毫秒级写入和高QPS查询;2. 写入优化:通过改进缓冲队列、连接池和COPY模式提高吞吐量和降低延迟;3. 消费优化:优化离线场景和分区表的消费逻辑,提升性能和资源利用率;4. 未来展望:进一步简化用户操作,支持更多DDL操作及全增量消费。Hologres 3.0全新升级为一体化实时湖仓平台,提供多项新功能并降低使用成本。
1252 1
Flink CDC + Hologres高性能数据同步优化实践
|
人工智能 API 语音技术
6.5K star!AI视频翻译配音神器,一键生成多平台适配内容,专业级本地化方案来袭!
KrillinAI 是一款基于 AI 大模型的视频翻译与配音工具,支持 12 种输入语言和 101 种输出语种,提供专业级翻译质量。其核心功能包括跨语言智能转换、全流程自动化处理及多项黑科技如语音克隆、术语替换等。技术架构涵盖 WhisperKit、OpenAI API 和 FFmpeg 等组件,实现从视频输入到多平台输出的一站式服务。项目已开源,详情见 GitHub 地址:https://github.com/krillinai/KrillinAI。
1074 1
|
消息中间件 架构师 Apache
一本书精通Apache RocketMQ
一本书精通Apache RocketMQ
628 3
|
人工智能 自然语言处理 计算机视觉
华为鸿蒙自己家的“AI”编辑器插件用起来到底怎么样?
编辑器AI插件如Codegeex、通义灵码等已问世,但通用性较强而不专精。华为推出的CodeGenie专为鸿蒙开发设计,集成在DevEco 5.0.0以上版本中,提供代码补全、生成等功能,尤其擅长处理鸿蒙相关问题,极大降低了鸿蒙开发的门槛。安装后需重启,支持自然语言生成代码,提升了开发效率。
1576 13
|
存储 JSON API
Python| 如何使用 DALL·E 和 OpenAI API 生成图像(1)
Python| 如何使用 DALL·E 和 OpenAI API 生成图像(1)
1368 7
Python| 如何使用 DALL·E 和 OpenAI API 生成图像(1)
|
存储 关系型数据库 Linux
2024 年 16 个适用于 Linux 的开源云存储软件 (上)
2024 年 16 个适用于 Linux 的开源云存储软件 (上)
1059 2
2024 年 16 个适用于 Linux 的开源云存储软件 (上)
|
Java Spring
ij社区版如何创建spring项目
如何在IntelliJ IDEA社区版中创建Spring项目,包括安装Spring Boot Helper插件的步骤和创建过程。
621 1
ij社区版如何创建spring项目
|
网络协议 算法 Linux
通过实验深入了解 TCP 数据的发送和接收
本系列文章是组内写给新人和实习生的 TCP入门系列教程,结合了理论和实践,本篇为第二篇,建议先读上篇《通过实验深入了解TCP 连接的建立和关闭》。