首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

在只包含1和0的数组中查找前1的索引,0都在数组的左侧,而所有的1都在右侧?

在只包含1和0的数组中查找前1的索引,0都在数组的左侧,而所有的1都在右侧。

要实现这个功能,可以使用二分查找的思想来解决。首先,我们需要定义两个指针,一个指向数组的开头,称为left指针,一个指向数组的末尾,称为right指针。

接下来,我们进行循环迭代的操作,直到left指针和right指针相遇。在每次循环中,我们取数组中间位置的索引mid,并获取该位置的值。如果mid位置的值为0,说明1在mid位置的右侧,因此我们将left指针移动到mid的右侧一位;如果mid位置的值为1,说明1在mid位置的左侧,因此我们将right指针移动到mid的左侧一位。

当left指针和right指针相遇时,即找到了数组中最后一个0的索引位置。此时,1的索引位置就是right指针的下一个位置。

下面是一个示例代码实现:

代码语言:txt
复制
def find_first_one(nums):
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == 0:
            left = mid + 1
        else:
            right = mid - 1

    return right + 1

# 示例输入
nums = [0, 0, 0, 0, 1, 1, 1, 1]
# 调用函数
result = find_first_one(nums)
# 输出结果
print("第一个1的索引位置为:", result)

该代码的时间复杂度为O(logN),其中N是数组的长度。该算法通过每次将搜索范围减半来快速定位到第一个1的位置。

腾讯云相关产品推荐:腾讯云云服务器、腾讯云云数据库、腾讯云人工智能、腾讯云物联网等产品。具体产品介绍和链接地址可以参考腾讯云官方网站。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

2023-01-06:给定一个只由小写字母组成的字符串str,长度为N, 给定一个只由0、1组成的数组arr,长度为N, arr == 0表示str中i位

2023-01-06:给定一个只由小写字母组成的字符串str,长度为N,给定一个只由0、1组成的数组arr,长度为N,arri等于 0 表示str中i位置的字符不许修改,arri 等于 1表示str中i...位置的字符允许修改,给定一个正数m,表示在任意允许修改的位置,可以把该位置的字符变成a~z中的任何一个,可以修改m次。...返回在最多修改m次的情况下,全是一种字符的最长子串是多长。1 1)。代码用rust和solidity编写。代码用rust编写。...'a'; aim 1(uint8(aim)+1)) {// 右边界// [l..r)int32 r = 0;// 用了几次修改了// change == m 用完的时候

1.1K10
  • 刷到 LeetCode 这个评论,我沉默了!

    首先给没有见过这道题目的小伙伴补充一下前置知识,这道题目讲的是: 一个长度为 n - 1 的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围 0 ~ n - 1 之内。...在范围 0 ~ n - 1 内的 n 个数字中有且只有一个数字不在该数组中,请找出这个数字。 比如数组为 [0,1,2,3,4,5,6,7,9],注意到 8 不在里面,因此输出 8 。...如果每一个数字都出现正确的位置上,即它们和索引之间的对应关系都是一样的,比如数字 0 出现在索引位置为 0 的地方、数字 1 出现在索引位置为 1 的地方、数字 2 出现在索引位置为 2 的地方。。。...而如果发现有数字没有出现在正确的位置上,也就是发生了错位,比如数字 9 出现在索引位置为 8 的地方,那么由于有且只有一个数字不在该数组中,那么很明显数字 10 出现在索引位置为 9 的地方、数字 11...1、一个部分上面所有的数字都在正确的位置上; 2、另外一部分上面所有的数字都不在正确的位置上 那么就利用二分法的思路,不断的缩小查找区间,也就能找到第一个发生了错位的数字。

    44540

    这些评论有点意思。

    首先给没有见过这道题目的小伙伴补充一下前置知识,这道题目讲的是: 一个长度为 n - 1 的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围 0 ~ n - 1 之内。...在范围 0 ~ n - 1 内的 n 个数字中有且只有一个数字不在该数组中,请找出这个数字。 比如数组为 [0,1,2,3,4,5,6,7,9],注意到 8 不在里面,因此输出 8 。...如果每一个数字都出现正确的位置上,即它们和索引之间的对应关系都是一样的,比如数字 0 出现在索引位置为 0 的地方、数字 1 出现在索引位置为 1 的地方、数字 2 出现在索引位置为 2 的地方。。。...而如果发现有数字没有出现在正确的位置上,也就是发生了错位,比如数字 9 出现在索引位置为 8 的地方,那么由于有且只有一个数字不在该数组中,那么很明显数字 10 出现在索引位置为 9 的地方、数字 11...1、一个部分上面所有的数字都在正确的位置上; 2、另外一部分上面所有的数字都不在正确的位置上 那么就利用二分法的思路,不断的缩小查找区间,也就能找到第一个发生了错位的数字。

    19050

    《Algorithms Unlocked》读书笔记2——二分查找和排序算法

    二分查找 在排好序的数组中查找目标值x。...// 利用二分法在已经排好序的数组中查找值x function binarySearch(array, x) { let p = 1; let r = array.length - 1;...// 把当前操作值保存到key中 let j = i - 1; // j 为当前值的前一位 // 在j大于等于0且前一位大于当前值时,前一位向右移动一个位置 while...合并:把子问题的解合并成原问题的解。 在归并排序中,我们把数组不断用二分法分解成两个小数组,直到每个数组只剩一个元素(基础情况)。再把小数组排好序并进行合并。...// 主元:数组中随机挑选单独的一个数(这里我们总是选数组中的最后一位)array[r] // 组L(左侧组):所有小于主元的数,array[p...q-1] // 组R(右侧组):所有大于或等于主元的数

    55030

    【算法】归并排序

    , 其合并两个数组时 , 不能在原数组中进行 ; 快速排序 , 始终都在原数组中进行 , 只涉及到交换数组中的元素 ; 正式由于该额外数组的存在 , 因此归并排序 , 并不是排序的最优算法 ; 算法要点...: 合并数组中 , 创建数组的时机 , 不要放在递归中 , 递归要调用很多次 , 频繁创建销毁数组 , 很耗费时间和空间 ; 代码示例 : class Solution { /**...; // 递归调用排序算法 mergeSort(A, 0, A.length - 1, mergeArray); } // 将 array 数组中 start...int start, int end, int[] mergeArray) { // 左右两个数组的遍历索引, 初值值为左右两侧的开始索引 int leftIndex =...mergeArray 数组中, 在将其设置到 array 数组中 for (int i = start; i <= end; i++) { array[i] =

    72810

    leetcode刷题(118)——除自身以外数组的乘积

    示例: 输入: [1,2,3,4] 输出: [24,12,8,6] 提示:题目数据保证数组之中任意元素的全部前缀元素和后缀(甚至是整个数组)的乘积都在 32 位整数范围内。...题解: 我们不必将所有数字的乘积除以给定索引处的数字得到相应的答案,而是利用索引左侧所有数字的乘积和右侧所有数字的乘积(即前缀与后缀)相乘得到答案。...方法一:左右乘积列表 1.初始化两个空数组 L 和 R。对于给定索引 i,L[i] 代表的是 i 左侧所有数字的乘积,R[i] 代表的是 i 右侧所有数字的乘积。...answer = new int[length]; // L[i] 为索引 i 左侧所有元素的乘积 // 对于索引为 '0' 的元素,因为左侧没有元素,所以 L[0]...i 左侧所有元素的乘积 // 因为索引为 '0' 的元素左侧没有元素, 所以 answer[0] = 1 answer[0] = 1; for (int

    27120

    备战蓝桥杯————二分查找(二)

    在本文中,我们将继续这一主题,不仅会回顾二分搜索的基本原理,还将重点介绍如何利用这一算法来寻找数组中目标值的右侧边界。通过对比左侧和右侧边界的搜索,我们将揭示二分搜索算法的灵活性和强大功能。...无论您是在准备技术面试,还是在日常编程中寻求效率提升,本文都将为您提供宝贵的洞见。 一、寻找右侧边界的二分查找         在有序数组中寻找特定值的右侧边界是二分查找算法的一个重要变体。...该方法返回一个包含两个元素的数组,第一个元素是目标值的最小索引(左侧边界),第二个元素是最大索引(右侧边界)。如果目标值不存在于数组中,则两个元素都为 -1。 以下是该方法的思路: 1....初始化变量: left 和 right 分别初始化为数组的起始索引和结束索引。 arr 是一个长度为 2 的数组,用于存储目标值的左侧和右侧边界索引。 2....返回结果: 返回包含左侧和右侧边界索引的数组arr。 这种方法确保了即使在目标值在数组中多次出现的情况下,也能正确地找到其首次和最后一次出现的索引。

    12610

    【二分算法】——8个题目让你找到二分算法的感觉势如破竹

    ; } // 如果没有找到目标值,返回 -1 return -1; } }; 2.在排序数组中查找元素的第一个和最后一个位置 https://leetcode.cn...如果数组中存在目标值,返回其索引;若不存在,返回其应该插入的位置。使用二分查找,找到第一个大于或等于目标值的位置。 步骤: 初始化: 使用 left 和 right 指针。...int mid = left + (right - left + 1) / 2; // 如果中间元素比左侧的前一个元素小,说明山峰在左边,右边界移动到...可以使用二分查找的变种。每次选择中点,如果中点比其右侧元素小,则峰值在右侧;如果中点比其右侧元素大,则峰值在左侧。这样逐步缩小搜索范围,直至找到峰值。...最小值通常出现在这两个有序子数组的交界处。可以使用二分查找,比较中点和右端点的值,若中点大于右端点,最小值在右侧;若中点小于右端点,最小值在左侧。

    34810

    除自身以外数组的乘积

    题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。 请不要使用除法,且在 O(n) 时间复杂度内完成此题。...,而是利用索引左侧所有数字的乘积和右侧所有数字的乘积(即前缀与后缀)相乘得到答案。...对于给定索引 i,L[i] 代表的是 i 左侧所有数字的乘积,R[i] 代表的是 i 右侧所有数字的乘积。     我们需要用两个循环来填充 L 和 R 数组的值。...// L[i] 为索引 i 左侧所有元素的乘积 // 对于索引为 '0' 的元素,因为左侧没有元素,所以 L[0] = 1 L[0] = 1;...} // 对于索引 i,除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积 for (int i = 0; i < length; i

    15230

    除自身以外数组的乘积

    示例: 输入: [1,2,3,4] 输出: [24,12,8,6] 提示:题目数据保证数组之中任意元素的全部前缀元素和后缀(甚至是整个数组)的乘积都在 32 位整数范围内。...既然是算除了自己之外的累乘,便可以以当前所在位置为分割点,分别计算左侧元素乘积 和 右侧元素乘积,之后再进行相乘。...对此由以下解法: 算法一(摘自LeetCode官方解法): 初始化两个空数组 L 和 R。对于给定索引 i,L[i] 代表的是 i 左侧所有数字的乘积,R[i] 代表的是 i 右侧所有数字的乘积。...两者交汇后,数组的值应填入最终值:因为左侧部分已经存储了左乘积,而即将计算得到右乘积;右侧部分已存储了右乘积,即将获得左乘积。故直接相乘即可。...空间复杂度:O(1),题目中所述,返回数组的空间不算,故所使用的额外存储空间为 left 和 right。故只有常数级别的空间复杂度。

    34610

    二分查找应用---有序数组中的单一元素

    题目 给定一个只包含整数的有序数组,每个元素都会出现两次,唯有一个数只会出现一次,找出这个数。...和 O(1)空间复杂度中运行。...示例 二分查找一般通过数组的中间元素 nums[mid] 判断 target 的位置(在 mid 位置,亦或是在 mid 的左侧或右侧),本题也不例外。 ?...),由于唯一的那个数一定存在于奇数长度的数组,因此丢弃偶数长度的子数组,在奇数长度的子数组中重复1和2; 3、若不等于两侧元素,则中间元素就是要查找的只出现一次的那个数字。...3、判断拆分后的两数组的长度,并移除偶数长度子数组; ? 4、在奇数长度的子数组中重复前1、2、3步; ? 查找过程完整动态展示 动态如下: ?

    72460

    二分查找应用---有序数组中的单一元素

    题目 给定一个只包含整数的有序数组,每个元素都会出现两次,唯有一个数只会出现一次,找出这个数。...image.png 二分查找一般通过数组的中间元素 nums[mid] 判断 target 的位置(在 mid 位置,亦或是在 mid 的左侧或右侧),本题也不例外。...),由于唯一的那个数一定存在于奇数长度的数组,因此丢弃偶数长度的子数组,在奇数长度的子数组中重复1和2; 若不等于两侧元素,则中间元素就是要查找的只出现一次的那个数字。...,并移除偶数长度子数组; image.png 4、在奇数长度的子数组中重复前1、2、3步; image.png 查找过程完整动态展示 动图如下: 动态0.gif Show me the Code...在排序数组中查找元素的第一个和最后一个位置 字节笔试题 leetcode 69. x 的平方根 二分查找 更多精彩 关注公众号【程序员小熊】 image.png

    64040

    【优选算法篇】剥洋葱式探索:用二分查找精准定位答案(下篇)

    前言: 二分查找是经典算法之一,以其高效的 O(log n) 时间复杂度在解决有序数据的查找问题中备受推崇。然而,面试和实际开发中,二分查找的基本用法往往不能满足复杂场景的需求。...例如,在一个升序数组中找到第一个大于等于目标值的位置。 搜索无序数据中的最优解:在一些单调性函数中,通过二分查找定位最优解。比如,最小化时间、成本等问题。...扩展至二维问题:如在行列有序的矩阵中查找特定元素,可以通过二分同时操作行和列。 进阶场景往往结合数学、逻辑优化,提升算法效率。 2. 题目1:山脉数组的峰顶索引 题目链接:852....空间复杂度:O(1),只使用了常数的额外空间。 4.4 补充(可看可不看) 4.4.1 暴力解法 暴力解法的核心思路是: 遍历数组:直接遍历数组中的每个元素,找到最小值。...最后 通过上述「二分查找在旋转排序数组中的应用」、「查找最小缺勤学生」及「寻找峰值元素」等例子,可以总结出二分查找算法的核心思想、应用场景和优化技巧。

    5600

    算法笔记(一)

    ,则意味着索引在左侧 right = middle - 1; // 将右区间挪到中间索引左侧 } else if (nums[middle] < target) { //...如果中间值小于目标值,则意味着索引在右侧 left = middle + 1; // 将左区间挪到中间索引右侧 } else { return middle; // 找到了目标值所在索引并返回...在排序数组中查找元素的第一个和最后一个位置 力扣题目链接[3] 给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。...需要处理的情况分为以下三种: 目标值比数组所有的值都大或者都小,此时返回[-1, -1]; 目标值存在于数组中,此时返回目标值的左右索引; 目标值介于数组之间但不存在,此时返回[-1, -1]。...螺旋矩阵 II 力扣题目链接[8] 给定一个正整数n,生成一个包含 1 到n^2所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。

    61810

    除自身以外数组的乘积(LeetCode 238)

    题目数据保证数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。 请不要使用除法,且在 O(n) 时间复杂度内完成此题。...<= 105 -30 <= nums[i] <= 30 保证数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内 进阶: 你可以在 O(1) 的额外空间复杂度内完成这个题目吗...,而是可以利用索引处左侧的所有数字乘积和右侧所有数字的乘积相乘得到答案。...对于给定索引 i,L[i] 代表的是 i左侧所有数字的乘积,R[i] 代表的是 i 右侧所有数字的乘积。 我们需要用两个循环来填充 L 和 R 数组的值。...具体步骤如下: 初始化 answer 数组,对于给定索引 i,answer[i] 代表的是 i 左侧所有数字的乘积。

    14410

    【C++】位运算

    因为整形的负数的二进制数是对正数的二进制数取反加一(先取反,所有的位数都不相同,+1后会发生进位,然后负数最右侧的1的左侧与正数相反,右侧与正数相同,都是0),然后&就会得到最右侧的1;可以画图试试。...true; } }; 丢失的数字 地址:. - 力扣(LeetCode) 给定一个包含 [0, n] 中 n 个数的数组 nums ,找出 [0, n] 这个范围内没有出现在数组中的那个数。...示例 1: 输入:nums = [3,0,1] 输出:2 解释:n = 3,因为有 3 个数字,所以所有的数字都在范围 [0,3] 内。2 是丢失的数字,因为它没有出现在 nums 中。...示例 2: 输入:nums = [0,1] 输出:2 解释:n = 2,因为有 2 个数字,所以所有的数字都在范围 [0,2] 内。2 是丢失的数字,因为它没有出现在 nums 中。...} }; 消失的两个数字 地址:. - 力扣(LeetCode) 给定一个数组,包含从 1 到 N 所有的整数,但其中缺了两个数字。

    7510
    领券