Easy

题目描述

给定一个二进制数组 nums 和一个整数 k，如果所有的 1 之间至少相距 k 个位置，则返回 true，否则返回 false。

示例 1：

输入：nums = [1,0,0,0,1,0,0,1], k = 2
输出：true
解释：每个 1 之间至少相距 2 个位置。

示例 2：

输入：nums = [1,0,0,1,0,1], k = 2
输出：false
解释：第二个 1 和第三个 1 只相距 1 个位置。

提示：

  • 1 <= nums.length <= 10^5
  • 0 <= k <= nums.length
  • nums[i] 是 0 或 1

解题思路

这道题要求检查数组中所有的 1 之间是否至少相距 k 个位置。

解题思路：

我们需要遍历数组，记录每个 1 的位置，然后检查相邻两个 1 之间的距离是否满足要求。

具体步骤：

  1. 遍历数组，找到第一个 1 的位置作为起始位置
  2. 继续遍历，每当遇到下一个 1 时，计算它与上一个 1 的距离
  3. 如果距离小于 k，则返回 false
  4. 更新上一个 1 的位置为当前位置
  5. 遍历完成后返回 true

时间复杂度分析： 只需要遍历一次数组，时间复杂度为 O(n) 空间复杂度分析： 只使用常数个变量，空间复杂度为 O(1)

这种方法简洁高效，是最优解法。

代码实现

class Solution {
public:
    bool kLengthApart(vector<int>& nums, int k) {
        int lastOne = -1;
        
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 1) {
                if (lastOne != -1 && i - lastOne - 1 < k) {
                    return false;
                }
                lastOne = i;
            }
        }
        
        return true;
    }
};

class Solution:
    def kLengthApart(self, nums: List[int], k: int) -> bool:
        last_one = -1
        
        for i, num in enumerate(nums):
            if num == 1:
                if last_one != -1 and i - last_one - 1 < k:
                    return False
                last_one = i
        
        return True

public class Solution {
    public bool KLengthApart(int[] nums, int k) {
        int lastOne = -1;
        
        for (int i = 0; i < nums.Length; i++) {
            if (nums[i] == 1) {
                if (lastOne != -1 && i - lastOne - 1 < k) {
                    return false;
                }
                lastOne = i;
            }
        }
        
        return true;
    }
}

var kLengthApart = function(nums, k) {
    let lastOne = -1;
    
    for (let i = 0; i < nums.length; i++) {
        if (nums[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历一次数组，n 为数组长度
空间复杂度O(1)只使用常数个变量存储上一个 1 的位置

相关题目