标签: data-structures

我看到了关于在 O(1) 时间内使用 findmin 设计堆栈的问题的答案：

/sf/answers/240519891/

如果请求相同怎么办：

Devise a stack-like data structure that does push, pop and min (or max) operations 
in O(1) time. There are no space constraints.

但deletemin也应该是O(1)？是否可以？

考虑一个问题有两个解决方案.

1. 执行n/2次即.如果n = 100则执行50次
2. 在sqrt中执行n次,即.如果n = 100则执行10次.

这两种解决方案都可以称为O(log N)吗？

如果是这样,则N和N/2的sqrt之间存在巨大差异.

如果我们不能说O(log N)那么我们可以说它是N吗？

但问题是这两者之间的差异.通过下面的图像,算法应该出现在这些解决方案中的哪一个？

请帮帮我.

说我有两个堆栈:

stack<int> s1, s2;

然后我在其中推送一些值:

s1.push(2);
s1.push(4);
s1.push(5);

s2.push(1);
s2.push(2);
s2.push(10);

当我像这样比较bool isEqual = (s1 > s2);它时,它会产生True.但为什么？并非所有s1的元素都大于相应的s2元素,并且所有元素的总和也不大于s2的元素.STL数据结构之间的确切比较方法是什么.

PS我想这也适用于队列,deques,列表.

将节点插入二叉搜索树的最坏情况时间复杂度是多少？

嘿伙计们，我明天有一个测验，我遇到了一些问题，寻找选择排序的递归程序的时间复杂度，任何人都可以解释它是如何 n^2 的。还有一个问题，一些排序算法循环的时间复杂度为 n/2，对于新手问题，/2 是什么意思。

#include <iostream>
using namespace std;

// recursive function to perform selection sort on subarray arr[i..n-1]
void selectionSort(int arr[], int i, int n)
{
    // find the minimum element in the unsorted subarray[i..n-1]
    // and swap it with arr[i]
    int min = i;
    for (int j = i + 1; j < n; j++)
    {
        // if arr[j] element is less, then it is the new minimum
        if (arr[j] < arr[min])
            min = j;    // update …

我正在寻找某种具有固定大小的地图,例如20个条目,但不仅如此,我想只保留最低值,让我说我正在评估某种功能并在我的地图中插入结果(我需要地图,因为我必须保持键值)但我想只有20个最低的结果.我正在考虑排序然后删除最后一个元素,但我需要为数百万条记录做,所以每次添加值时排序效率不高,也许有更好的方法？感谢帮助.

假设有一大堆范围.例如,大小为5000的集合:

[100,200],[1,59],[3,5],[70,70]...

如何在Java中检查整数n是否有效地落入这些范围中的至少一个？

所以我很困惑,需要一个建议.在Java中,我可以实现自己的Stack,或者我可以使用java.util提供的Stack.

手册:

public class stack {

private int maxSize; //max size of stack
private char[] stackArray;
private int top; //index poistion of last element

public stack(int size){
    this.maxSize=size;

    this.stackArray=new char[maxSize];
    this.top=-1; //    
}


public void push(char j){

    if (isFull()) {
        System.out.println("SORRY I CANT PUSH MORE");
    }else{

    top++;
    stackArray[top]=j;
    }
}

public char pop(){

    if(isEmpty()){
        System.out.println("Sorry I cant pop more!");
        return '0';
    }else{

       int oldTop=top;
    top--;
    return stackArray[oldTop];

    }
}


public char peek(){
    if(!isEmpty()) {
        return stackArray[top];
    }
}


public boolean …

在 C++ 中：

• 列表是可以按顺序包含非唯一值的集合

• 多重集是一个可以按顺序包含非唯一元素的集合

那么两者的具体区别是什么呢？为什么我会在另一个上使用？

我曾尝试在网上查找此信息，但大多数参考资料（例如 cplusplus.com）以不同的方式谈论这两个容器，因此差异并不明显。

就数据结构而言，C ++中的std :: set不是真正的集合。std :: unordered_set是一个实数集，但std :: set是一个二叉搜索树，更具体地说是一棵红黑树。那么为什么将其称为std :: set？是否有一些特定功能可以将std :: set与二叉树区分开？谢谢。