给定具有正整数和负整数的无限长度排序数组.在其中找到一个元素.

编辑
数组中的所有元素都是唯一的,并且数组在正确的方向上无限.

有两种方法:

方法1:

将索引设置在位置100,如果要找到的元素较少,则在前100个项目中进行二进制搜索,否则将下一个索引设置在位置200处.这样,继续将索引增加100,直到项目更大.

方法2:

设置索引的幂2.首先将索引设置在位置2,然后是4,然后是8,然后是16,依此类推.再次从位置2 ^ K到2 ^(K + 1)进行二元搜索,其中项目位于其间.

在最佳情况和最差情况下,这两种方法中的哪一种会更好？

给定一个具有正整数和负整数的数组,将所有奇数索引元素移动到左侧,甚至将索引元素移动到右侧.

问题的难点在于在维持秩序的同时就地完成.

例如

7, 5, 6, 3, 8, 4, 2, 1

输出应该是:

5, 3, 4, 1, 7, 6, 8, 2

如果顺序无关紧要,我们可以使用快速排序的partition()算法.

如何在O(N)中完成？

我对sizeof操作员的评估时间感到困惑.
什么时候对sizeof运算符进行求值？

它的评估时间[ compile-time or run-time] 是否取决于语言[ C? C++?]？

我们可以sizeof在运行时[ in C++] 创建的对象中使用吗？

这可能是微软面试的问题.

从排序的数组中找出第k个最小元素(忽略重复).
[编辑]:数组可能包含重复项(未指定).

想了很多次,但仍在质疑自己:是否还有更好的解决方案？

方法1:

获取最大堆并插入前k个独特元素[可以轻松检查].堆化堆.
现在,当一个新元素小于堆的头部时,用这个新元素替换head将它堆积起来.最后,如果堆的大小为k,则堆的头指示第k个最小元素.否则,第k个最小元素不存在.

时间复杂度:O(NlogK)
空间复杂度:O(K)

方法2 [更好的方法]:

这些元素可能是正确的.因此,通过与之前的元素进行比较来检查唯一元素,并在目前为止找到的唯一变量计数为k时停止.
时间复杂度:O(N)
空间复杂度:O(1)

方法3 [更好的方法(可能)]:

也可以使用快速排序分区算法的修改版本.但是,由于阵列已经排序,可能会导致最坏的情况.
这里出现两个问题:
1.如果数组包含重复项,它是否有效？
2. 难道比我的第二个apporach更好？

我想知道是否存在任何O(logn)解决方案？

我收到以下错误:
prog.cpp:在成员函数'void Sequence :: GetSequence()':
prog.cpp:45:错误:'itoa'未在此范围内声明

我有包含cstdlib头文件,但它无法正常工作.

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <functional>
using namespace std;

template<typename T>
struct predicate :
public binary_function<T, T, bool>
{
    bool operator() (const T& l,const T &r) const
    {
          return l < r;
    }
};

class Sequence
{
    public:
    Sequence(vector<string> &v)
    { /* trimmed */ }

void GetSequence(void)
{
    string indices = "";
    char buf[16];

    for( map<int, string>::iterator
            i = m.begin(); i != m.end(); ++i )
    {
indices …

为什么编译时间和加载时间地址绑定生成相同的物理和逻辑地址,而执行时地址绑定生成不同的物理和逻辑地址？

我在编码比赛中遇到了这个puzzle问题related to data structure.

有一个树木的星球(真正的树木不是树木数据结构!!).它有数十亿甚至数万亿的树木.国王命令用碳约会找到所有树木的年龄中位数(年和整数).(Method does not matter.)注意:中位数是排序的数字列表中的"中间数字".

限制因素:
1.已知最古老的树已有 2000年的历史.
2.他们有一台机器可以存储从-infinity到+ infinity范围内的整数.
3.但是一次可以存储在内存中的这种整数的数量是100万.

因此,一旦您存储了100万个整数来存储下一个整数,您必须删除已存储的整数.
所以不知何故,他们必须跟踪中位数,因为他们继续计算树木的年龄.
他们怎么能这样做？

我的方法
使用外部排序的变体来对块中的年龄进行排序并将它们写入文件中.
应用k-way合并[用于块].
上述方法的问题是它需要对文件进行两次扫描.

我可以想到另一种使用信息的方法The oldest tree is known to be 2000 years old.
我们不能拿一个count array[ as range of ages of tree is fixed]？

我想知道有没有更好的方法？
是否存在我们不需要将数据存储在文件中的方法？[ where only main memory is sufficient?]

我在这里找到了这个问题,但这不是我要找的答案.因此,再次发布.

形式的功能:

F( N ) = rank

表示给定N十进制表示的数字,其等级为:

Starting from 0 to N, how many numbers are there with same number of set bits in its
binary representation.

我将通过一个例子来说明问题.

N = 6 ( 0110 )
Its rank is 3.
1. 3 ( 0011 )
2. 5 ( 0101 )
3. 6 ( 0110 )

现在,给出一个数字,找到它的排名.

显而易见的方法是从0开始并检查每个数字的设置位数N-1.

问题是:

有没有logN解决方案？

阅读pointers&之间的很多差异references.

以下是我学到的内容的简要说明.

1.定义指针时分配内存.但是,引用是名称别名,因此没有为它分配内存(Is it correct?).

2.必须在定义时初始化引用,因为引用是使用常量指针实现的,因此不能指向另一个对象.然而,指针在定义时不需要初始化,因此也可以改变为指向某个其他对象.

3.引用自动被取消引用.当你写作cout << p; 它由编译器自动解除引用并视为cout << *p; 由编译器.

这里,p是参考.

1. 无法引用引用.无论何时,您声明对引用的引用,它实际上是对同一变量的引用.例如

   int i;    
   int &r1=i;    
   int &r2=r1; <-------------------2
   

   Run Code Online (Sandbox Code Playgroud)

编译器将语句2解释为:
int&r2 =(*r1)
和(*r1)只是变量i本身.

然而,指向指针的指针是可能的.

5.指针数组是可能的,而引用数组是不可能的(为什么？).

6.指针的地址是可能的.无法提供参考地址.它给出了变量的地址.

7.在某些情况下,您必须使用引用.您不能在那里使用指针.考虑以下示例:

A a = b + c;

其中a,b,c是A类的对象.运算符'+'按如下方式重载:

const A& operator+(const A& o)
{
     return A(i+o.i);
}

请参阅示例代码:http: //ideone.com/Q0pE1

这里参数列表中的引用用于保存内存占用.
您不能在参数列表中使用指针,因为您必须在运算符函数中传递对象的地址.
A =&b +&c;
但是,如果在参数列表中使用指针,那么我们最终将添加地址而不是对象本身.

我想知道我还缺少其他任何一点吗？

什么时候应该去指针和什么时候参考？

fun()Derived类中的方法是私有的.当我们ptr->fun()通过运行时多态来调用函数时,它正在执行.但这违反了Derived类的封装属性.

#include<iostream>
using namespace std;

class Derived;

class Base {
private:
    virtual void fun() { cout << "Base Fun"; }
friend int main();
};

class Derived: public Base {
private:
    void fun() { cout << "Derived Fun"; }
};

int main()
{
Base *ptr = new Derived;
ptr->fun();
return 0;
}

有人可以解释一下发生了什么吗？