标签: space-complexity

我只想知道,当后缀树优于增强后缀数组时.

在阅读了使用增强的suf fi x数组替换suf fi x树之后,我再也看不到使用后缀树的理由了.有些方法可能会变得复杂,但您可以使用后缀数组执行所有操作,使用后缀树可以执行的操作,并且需要相同的时间复杂度但内存较少.

一项调查甚至表明,后缀数组更快,因为它们缓存更友好,并且不会产生更多的缓存未命中,然后产生后缀树(因此缓存可以更好地预测数组使用,然后在递归树结构上).

那么,有没有人知道在后缀数组上选择后缀树的原因？

编辑 好的,如果你知道更多告诉我,到目前为止:

• 后缀不允许在线构造
• 一些模式匹配算法在Suffixtrees上运行得更快
• (补充)由于在线构造,你可以将它保存在高清上并扩大现有的后缀树.如果你使用SSD,它也应该安静快速.

我遇到了以下问题.

给定n个元素的数组和整数k,其中k < n.元素{ a ₀ ... a _k }和{ a _{k +1} ... a _n }已经排序.给出一个算法在O(n)时间和O(1)空间中排序.

在我看来,它不能在O(n)时间和O(1)空间中完成.问题实际上似乎是询问如何进行mergesort的合并步骤,而不是就地.如果有可能,那么不会以这种方式实现mergesort吗？我无法说服自己,但需要一些意见.

您将获得一个整数数组.您必须输出最大范围,以便该范围内的所有数字都存在于数组中.这些数字可能以任何顺序出现.例如,假设数组是

{2, 10, 3, 12, 5, 4, 11, 8, 7, 6, 15}

在这里,我们找到两个(非平凡的)范围,这些范围中的所有整数都存在于数组中,即[2,8]和[10,12].其中[2,8]是较长的一个.所以我们需要输出它.

当我收到这个问题时,我被要求在线性时间内完成此操作而不使用任何排序.我认为可能存在基于散列的解决方案,但我无法想出任何东西.

这是我尝试解决方案:

void printRange(int arr[])
{
    int n=sizeof(arr)/sizeof(int);
    int size=2;
    int tempans[2]; 

    int answer[2];// the range is stored in another array
    for(int i =0;i<n;i++)
    {
        if(arr[0]<arr[1])
        {
             answer[0]=arr[0];
             answer[1]=arr[1];
        }
        if(arr[1]<arr[0])
        {
            answer[0]=arr[1];
            answer[1]=arr[0];
        }

        if(arr[i] < answer[1])
            size += 1;
        else if(arr[i]>answer[1]) {
            initialize tempans to new range;
             size2=2;
        }
        else { 
            initialize tempans  to new range
        }
}

//I have to check when the count …

给定nxm的矩阵填充0和1

例如:

1 1 0 1 0

0 0 0 0 0

0 1 0 0 0

1 0 1 1 0

如果矩阵在(i,j)处有1,则用1​​填充列j和行i

即,我们得到:

1 1 1 1 1

1 1 1 1 0

1 1 1 1 1

1 1 1 1 1

所需复杂度:O(n*m)时间和O(1)空间

注意:您不能在矩阵条目中存储除"0"或"1"之外的任何内容

以上是Microsoft面试问题.

我想了两个小时了.我有一些线索,但不能再继续了.

好.这个问题的第一个重要部分是Even using a straight forward brute-force way,它不容易解决.

如果我只使用两个循环迭代矩阵中的每个单元格,并更改相应的行和列,则无法完成,因为生成的矩阵应基于原点矩阵.

例如,如果我看到a[0][0] == 1,我无法改变row 0和column 0所有1,因为这将影响row 1因为row 1原来没有0.

我注意到的第二件事是,如果一行r只包含 …

维基百科将中位数中值算法列为需要O(1)辅助空间.

但是,在算法的中间,我们对一个大小的子数组进行递归调用,n/5以找到中位数的中位数.当这个递归调用返回时,我们使用返回的中位数中值作为分区数组的轴.

此算法是否将O(lg n)激活记录作为递归的一部分推送到运行时堆栈？从我所看到的,这些递归调用以找到连续的中位数中位数不能被尾调用优化,因为我们在递归调用返回后做了额外的工作.因此,似乎这个算法需要O(lg n)辅助空间(就像Quicksort,O(lg n)由于运行时堆栈使用的空间,维基百科列为需要辅助空间).

我错过了什么,或维基百科文章错了吗？

(注意:我所指的递归调用是return select(list, left, left + ceil((right - left) / 5) - 1, left + (right - left)/10)在维基百科页面上.)

存在与阵列相关的问题,要求时间复杂度为O(n)且空间复杂度为O(1).

如果我使用Arrays.sort(arr),并使用for循环到一个传递循环,例如:

public static int hello(int[]A){
  Arrays.sort(A);
  for(int i=0;i<A.length;i++){
     ....................
  }
  return ....;

}

因此循环将花费O(n)时间.我的问题是:会Arrays.sort()花更多的时间吗？如果我使用Arrays.sort(),这次复杂性仍然是O(n)吗？会Arrays.sort()花费更多的空间吗？

我很想知道哪种算法更好:

• 具有O(n log n)时间和O(1)空间复杂度的算法
• 具有O(n)时间和O(n)空间复杂度的算法

在O(n long n)时间和恒定空间中求解的大多数算法可以在O(n)时间内通过在空间方面支付罚分来求解.哪种算法更好？我如何决定这两个参数？

示例:数组对总和

1. 可以通过排序在O(n logn)时间内解决
2. 可以在O(n)时间使用散列映射来解决,但是使用O(n)空间

给定一个数组,其中每个数字的出现次数是奇数,除了一个出现次数是偶数的数字.找到偶数出现的数字.

例如

1, 1, 2, 3, 1, 2, 5, 3, 3

输出应该是:

2

以下是限制:

1. 数字不在范围内.
2. 就地做.
3. 所需的时间复杂度为O(N).
4. 数组可能包含负数.
5. 数组未排序.

由于上述限制,我的所有想法都失败了:基于比较的排序,计数排序,BST,散列,暴力.

我很想知道:XORing会在这里工作吗？如果有,怎么样？

我理解基本的,如果我有这样的功能:

int sum(int x, int y, int z) {
  int r = x + y + z;
  return r;
}

它需要3个单位的空间用于参数,1个用于局部变量,这永远不会改变,所以这是O(1).

但是,如果我有这样的功能怎么办:

void add(int a[], int b[], int c[], int n) {
    for (int i = 0; i < n; ++i) {
        c[i] = a[i] + b[0]
    }
}

其中需要N个单位a,M个单位为bL个单位c,1个单位为i和n.所以它需要N+M+L+1+1大量的存储空间.

那么这里的空间复杂性大O会是什么？需要更高记忆的那个？也就是说,如果N比M和L更高的momery(从更高的意义上假设大于10**6) - 那么可以说空间复杂性是否O(N)与我们对时间复杂性的影响一样？

但是如果所有三个即a,b,c都没有太大差异

喜欢这个功能

void multiply(int a[], int b[], int c[][], …

最近在一次采访中有人问我这个问题：

给定两个字符串s和t，当将它们输入到空文本编辑器中时，返回它们是否相等。＃表示退格字符。

Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

我想出了以下解决方案，但空间效率不高：

  public static boolean sol(String s, String t) {
    return helper(s).equals(helper(t));
  }

  public static String helper(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
      if (c != '#')
        stack.push(c);
      else if (!stack.empty())
        stack.pop();
    }
    return String.valueOf(stack);
  }

我想看看是否有更好的方法可以解决不使用堆栈的问题。我的意思是我们可以解决O（1）空间复杂性吗？

注意：我们也可以包含多个退格字符。