旋转阵列中的最长子阵列
Longest sub array in rotating array
有没有办法在 log(n) 时间内找到 1 的最长子数组？
示例：
110011111000 - 那么输出是 5（从 pos 5 到 10）
1110011101 - 这里的输出是 3 但在旋转 1 之后数组变为 111100111 并且输出现在是 4.
001111 - 这里的输出是从 pos 3 到 6 的 4 但旋转后它从 pos 4 到 6 变成 3
注意：我在旋转前找到O(n)中最长的子数组长度。如果我有过去的结果，如何改进旋转后的解决方案？
不行，因为你必须知道每一个字母的值才能算1s，至少是O(n)。
您可以按照以下步骤操作：
- 找到 1 的最长子数组（O(n)）。在该循环中找到 0.
的第一个和最后一个实例
- 开始旋转并更新这些参数。
- 如果最后一个索引为 0，则搜索前一个 1 以保持更新参数（在复杂度上，这不会超过 O(n) 总计。
我假设您知道如何获取最大子数组索引并在 O(n) 中进行计数。除此之外，您还需要找到第二大子数组（可以在同一个循环中完成）。
让我们再提取 2 个参数 - 第一个和最后一个零（简单代码 - 如果你需要，我可以附加它）
旋转数组时有3个选项：
- 没有变化
- 创建了更大的子数组
- 当前最大的子数组中断
第一种和第二种情况——你只需要更新参数——O(1)——你可以根据你的参数知道是这种情况。在第三种情况下，您将需要使用找到的第二长子数组（注意一次只能打断 1 个子数组）
例如，假设您有数组：1110011101（作为您的示例）并且您有 max = 3 和 maxIndex = 5。在 运行 之后 getZeroIndexs 函数你还知道 firstZeroIndex = 3 和 lastZeroIndex = 8.
旋转后我们的变量会是什么样子？
max = 3
maxIndex = 6
firstZeroIndex = 4 // this will increase as long as the lastZeroIndex different then the array size
lastZeroIndex = 9 //this will go up till array.size - when it those you need to loop again till you find last
在这种情况下，第一个索引移动到 4 是什么使他比 max 大 -> max = 4 和 maxIndex = 0。
现在你的数组是：1111001110 所以 lastZeroIndex = 9 作为数组大小所以下一次旋转将产生：
max = 4
maxIndex = 1
firstZeroIndex = 0
lastZeroIndex = ? // here you need to loop from the end of your array till you get 0 -> O(k) in total complexity, all the run together will be O(n)
希望说清楚，如果不明白欢迎追问！
有没有办法在 log(n) 时间内找到 1 的最长子数组？
示例：
110011111000- 那么输出是 5（从 pos 5 到 10）1110011101- 这里的输出是 3 但在旋转 1 之后数组变为111100111并且输出现在是 4.001111- 这里的输出是从 pos 3 到 6 的 4 但旋转后它从 pos 4 到 6 变成 3
注意：我在旋转前找到O(n)中最长的子数组长度。如果我有过去的结果，如何改进旋转后的解决方案？
不行，因为你必须知道每一个字母的值才能算1s，至少是O(n)。
您可以按照以下步骤操作：
- 找到 1 的最长子数组（O(n)）。在该循环中找到 0. 的第一个和最后一个实例
- 开始旋转并更新这些参数。
- 如果最后一个索引为 0，则搜索前一个 1 以保持更新参数（在复杂度上，这不会超过 O(n) 总计。
我假设您知道如何获取最大子数组索引并在 O(n) 中进行计数。除此之外，您还需要找到第二大子数组（可以在同一个循环中完成）。
让我们再提取 2 个参数 - 第一个和最后一个零（简单代码 - 如果你需要，我可以附加它）
旋转数组时有3个选项：
- 没有变化
- 创建了更大的子数组
- 当前最大的子数组中断
第一种和第二种情况——你只需要更新参数——O(1)——你可以根据你的参数知道是这种情况。在第三种情况下，您将需要使用找到的第二长子数组（注意一次只能打断 1 个子数组）
例如，假设您有数组：1110011101（作为您的示例）并且您有 max = 3 和 maxIndex = 5。在 运行 之后 getZeroIndexs 函数你还知道 firstZeroIndex = 3 和 lastZeroIndex = 8.
旋转后我们的变量会是什么样子？
max = 3
maxIndex = 6
firstZeroIndex = 4 // this will increase as long as the lastZeroIndex different then the array size
lastZeroIndex = 9 //this will go up till array.size - when it those you need to loop again till you find last
在这种情况下，第一个索引移动到 4 是什么使他比 max 大 -> max = 4 和 maxIndex = 0。
现在你的数组是：1111001110 所以 lastZeroIndex = 9 作为数组大小所以下一次旋转将产生：
max = 4
maxIndex = 1
firstZeroIndex = 0
lastZeroIndex = ? // here you need to loop from the end of your array till you get 0 -> O(k) in total complexity, all the run together will be O(n)
希望说清楚，如果不明白欢迎追问！