我有一个只包含0和1的数组。我需要找到包含相等数量的0和1的最大子数组。一种朴素的方法是使用复杂度为O(n^2)
的算法,在外层循环中遍历每个元素,在内层循环中计算可能的子数组并更新最大大小,如果找到的话。是否有其他更好的方法(类似于O(n))可以使用?谢谢!
Input: arr[] = {1, 0, 1, 1, 1, 0, 0}
Output: 1 to 6 (Starting and Ending indexes of output subarray)
这是一个O(n)时间复杂度和O(n)空间复杂度的算法。我不确定它是否最优,但它可以避免二次时间复杂度。
基本思路如下:假设你从数组的左边开始扫描到右边,在每一步记录1的数量与0的数量之间的差异。如果你在每个步骤中写出这些值,你会得到像这样的东西:
1, 0, 1, 0, 0, 0, 0
0, 1, 0, 1, 0, -1, -2, -3
如果你有一个由相同数量的0和1组成的子数组,那么子数组开始时0和1的净差将等于子数组后面的净数。因此,可以将此问题重新构造为试图找到两个在辅助数组中相等且尽可能远离的值。
好消息是数组中的每个条目都介于-n和+n之间,因此可以制作一个2n+1元素表格,并在其中存储每个数字第一次和最后一次出现的索引。从那里开始,很容易找到最长的范围。总体而言,这需要O(n)空间,并且所有内容都可以在O(n)时间内填充和搜索。
希望这能帮到你!
首先将您的零转换为-1。然后,您需要寻找零和的最大子数组。这个算法可以在这里找到。
public int equalNumber(int arr[]){
int sum[] = new int[arr.length];
sum[0] = arr[0] == 0? -1 : 1;
for(int i=1; i < sum.length; i++){
sum[i] = sum[i-1] + (arr[i] == 0? -1 : 1);
}
Map<Integer,Integer> pos = new HashMap<Integer,Integer>();
int maxLen = 0;
int i = 0;
for(int s : sum){
if(s == 0){
maxLen = Math.max(maxLen, i+1);
}
if(pos.containsKey(s)){
maxLen = Math.max(maxLen, i-pos.get(s));
}else{
pos.put(s, i);
}
i++;
}
return maxLen;
}
解决方案是什么?
因此,在这个解决方案中,它将考虑所有的子数组,并且对于每个子数组,它将计算出其中存在的0和1的总数。如果子数组包含相同数量的0和1,则根据需要更新最大的数组。 该解决方案的时间复杂度为O(n^3),因为在n个元素的数组大小中有n^2个子数组,而找到0和1的计数需要O(n)。我们可以通过在常量时间内计算0和1的计数来优化方法,使其运行O(n^2)。
我们如何解决这个问题?
在这里,我们可以使用映射来在线性时间内解决它。想法是用-1替换0,并找到具有0总和的最大子数组。
因此,为了找到最大子数组,请创建一个空映射,该映射将存储具有给定总和的第一个子数组的结尾。然后遍历给定的数组并在元素中维护总和。
class Solution {
// Function to find the largest subarray having an equal number
// of 0's and 1's
public static void findLargestSubarray(int[] nums)
{
// create an empty `HashMap` to store the ending index of the first
// subarray having some sum
Map<Integer, Integer> map = new HashMap<>();
// insert (0, -1) pair into the set to handle the case when a
// subarray with zero-sum starts from index 0
map.put(0, -1);
// `len` stores the maximum length of subarray with zero-sum
int len = 0;
// stores ending index of the largest subarray having zero-sum
int end_index = -1;
int sum = 0;
// Traverse through the given array
for (int i = 0; i < nums.length; i++)
{
// sum of elements so far (replace 0 with -1)
sum += (nums[i] == 0)? -1: 1;
// if the sum is seen before
if (map.containsKey(sum))
{
// update length and ending index of largest subarray having zero-sum
if (len < i - map.get(sum))
{
len = i - map.get(sum);
end_index = i;
}
}
// if the sum is seen for the first time, insert the sum with its
// index into the map
else {
map.put(sum, i);
}
}
// print the subarray if present
if (end_index != -1)
{
System.out.println("[" + (end_index - len + 1) + ", " +
end_index + "]");
}
else {
System.out.println("No subarray exists");
}
}
def check_max_length(input_array):
length = len(input_array)
mapping_dict = {}
max_length = 0
for i in range(length):
if input_array[i] not in mapping_dict.keys():
mapping_dict[input_array[i]] = i
else:
max_length = max(max_length,i-mapping_dict[input_array[i]])
return max_length
def find_max_substring_length(input_string):
def_array = [0]
zero_count = 0
one_count = 0
# difference between number of zeroes and ones
def_zero_one = 0
for i in range(len(input_string)):
if input_string[i] == '1':
one_count+=1
else:
zero_count+=1
def_array.append(one_count-zero_count)
max_substring = check_max_length(def_array)
return max_substring
input_string = '1000100'
substring_length = find_max_substring_length(input_string)
print(substring_length) // will give result as 2
class Solution {
public:
int findMaxLength(vector<int>& nums) {
int n=nums.size();
if(n<=1) return 0;
vector<int> arr(n,-1);
arr[0]= (nums[0]==0)? -1:1 ;
for(int i=1;i<n;i++)
{
arr[i] = arr[i-1] + ((nums[i]==0)? -1 : 1) ;
}
int sol=0;
unordered_map<int,int> mp;
for(int i=0;i<n;i++)
{
if(arr[i]==0) sol = i+1;
else
{
if(mp.find(arr[i])==mp.end())
{
mp[arr[i]]=i;
}
else
{
sol=max(sol,i-mp[arr[i]]);
}
}
}
return sol;
}
};
使用O(n)时间实现哈希映射。
int count=0, max_length=0;
unordered_map<int,int> mp;
mp[0] = -1;
for(int i=0; i<nums.size(); i++)
{
if(nums[i] == 0) count += -1;
if(nums[i] == 1) count += 1;
if(mp.find(count) != mp.end())
max_length = max(max_length, i-mp[count]);
else
mp[count] = i;
}
return max_length;
这是一个经过测试的解决方案。
/**
* given an array of 0's and 1's return the length of the maximal
* subarray that has only 0's and 1's
* O(n) solution inspired by https://dev59.com/010Z5IYBdhLWcg3wrByH#31201586
*
* in 0 0 1 1
* aux 0 -1 -2 -1 0
* @param in
* @return
*/
static int lenMaxSubArray(int[] in) {
int maxLen = -1;
int[] oneCount = new int[in.length + 1];
oneCount[0] = 0;
for (int i = 0; i < in.length; i++) {
if (in[i] == 1) {
oneCount[i + 1] = oneCount[i] + 1;
} else {
oneCount[i + 1] = oneCount[i] - 1;
}
}
Map<Integer, List<Integer>> map = new HashMap<>();
for (int i = 0; i < oneCount.length; i++) {
List<Integer> list = map.getOrDefault(oneCount[i], new ArrayList<>());
list.add(i);
map.put(oneCount[i], list);
}
for (int i = 0; i < oneCount.length; i++) {
List<Integer> list = map.get(oneCount[i]);
if (list != null) {
int start = list.get(0);
int end = list.get(list.size() - 1);
maxLen = Math.max(maxLen, end - start);
}
}
return maxLen;
}
使用 JavaScript 实现 @templatetypedef 算法,并修改为使用 map 来帮助查找最大长度
function findMaxLen(a) {
// secondary array, initialized with the first element as 0
let b = [0]
let sum = 0
// populate the secondary array and update the sum as per the algorithm
for (let i = 0; i < a.length; i++) {
b[i + 1] = a[i] == 0 ? sum - 1 : sum + 1
sum = b[i + 1]
}
// map of sum vs the first index of the secondary array with the sum value
let map = new Map()
let maxLen = 0
for (let i = 0; i < b.length; i++) {
if (map.has(b[i]))
maxLen = Math.max(maxLen, i - map.get(b[i]))
else
map.set(b[i], i)
}
return maxLen
}
算法
我们使用HashMap映射来以(index,count)的形式存储条目。每当遇到一个计数时,我们在映射中创建一个条目,并稍后使用相应的索引来查找具有相等数量的零和一的最大子数组的长度,当再次遇到相同的计数时。
public class Solution {
public int findMaxLength(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
int maxlen = 0, count = 0;
for (int i = 0; i < nums.length; i++) {
count = count + (nums[i] == 1 ? 1 : -1);
if (map.containsKey(count)) {
maxlen = Math.max(maxlen, i - map.get(count));
} else {
map.put(count, i);
}
}
return maxlen;
}
}
Time complexity : O(n). The entire array is traversed only once.
Space complexity : O(n). Maximum size of the HashMap map will be n, if all the elements are either 1 or 0.
0 0 0 0 1 0 1 0 0 0
- Piyush Srivastava