A simple bit array caused memory limit exceed, anyone please?


  • 0
    D

    hi

    Anyone kindly let me know why below code are memory limit exceed? I use bit array and the maximize size is 4^10 = 2^20 = 2097152 bit = 256k

    public class Solution
    {
    
        private bool[] bit_cache = new bool[2 << 20];
        public IList<string> FindRepeatedDnaSequences(string s)
        {
            if (s.Length < 10) return null;
    
            for (int i = 0; i < bit_cache.Length; i++)
            {
                bit_cache[i] = false;
            }            
            
            IList<String> res = new List<String>();
    
            char[] arr = s.ToCharArray();
    
            for (int i = 9; i < arr.Length; i++)
            {
                int num = 0;
                
                for (int j = i-9; j <= i; j++)
                {
                    num <<= 2;
                    switch (arr[j])
                    {
                       case 'C': num |= 1; break;
                       case 'G': num |= 2; break;
                       case 'T': num |= 3; break; 
                    }
                }
                
                if (bit_cache[num] == false)
                {
                    bit_cache[num] = true;
                }
                else {
                    StringBuilder sb = new StringBuilder();
                    for (int j = i - 9; j <= i; j++)
                    {
                        sb.Append(arr[j]);
                    }
                    res.Add(sb.ToString());
                }
            }
    
            return res;
        }
    
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.