精华内容
下载资源
问答
  • 1785 数据流中的算法 51nod近日上线了用户满意度检测工具,使用高级...加一个新feature,即在统计均值的同时,计算窗口中满意程度的标准差和中位数(均值需要向下取整)。 输入 第一行是整数n与k,代表有n次操...

    1785 数据流中的算法

     

    51nod近日上线了用户满意度检测工具,使用高级人工智能算法,通过用户访问时间、鼠标轨迹

    等特征计算用户对于网站的满意程度。

    现有的统计工具只能统计某一个窗口中,用户的满意程度的均值。夹克老爷想让你为统计工具添

    加一个新feature,即在统计均值的同时,计算窗口中满意程度的标准差和中位数(均值需要向下取整)。

    输入

    第一行是整数n与k,代表有n次操作,时间窗口大小为k。 
    (1 <= n <= 10^6, 1 <= k <= 100)
    
    接下来的n行,每行代表一次操作。操作有“用户访问”、“查询均值”、“查询方差”、“查询中位数”四种。
    每行的第一个数代表操作类型。
    
    操作数1:用户访问
    输入格式:<1, v>
    用户的满意度v为闭区间[0, 100]中的任意整数。用户每访问一次,数据更新,移动统计窗口。
    
    操作数2:查询均值
    输入格式:<2>
    统计窗口内的用户满意度的均值。
    
    操作数3:查询方差
    输入格式:<3>
    统计窗口内用户满意度的方差
    
    操作数4:查询中位数
    输入格式:<4>
    统计窗口内用户满意度的中位数
    
    p.s. 在有查询请求时,窗口保证不为空
    p.s.s. 有查询请求时,窗口可能不满

    输出

    对于“查询均值”、“查询方差”、“查询中位数”操作的结果,输出保留两位小数。

    输入样例

    12 3
    1 1
    1 2
    1 3
    2
    3
    4
    1 4
    1 5
    1 6
    2
    3
    4

    输出样例

    2.00
    0.67
    2.00
    5.00
    0.67
    5.00

    思路描述:

            显然,对本题而言,均值和方差(D(X)=E^{2}(X)-E(X)^{2})的维护是很简单的,

    难点在于中位数的维护,考虑只有100个数,1e6次查询,所以用set维护这最多100个数

    即可,时间复杂度O(q*100*log_{2}100) 。本题用VC++交更容易过,C++卡了输入。

            当然,也可以直接线段树维护中位数,O(q*log_{2}100) 。

    代码实现(multiset):

    #include<iostream>
    #include<stdio.h>
    #include<cmath>
    #include<set>
    #include<algorithm>
    #define LL long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N=2e6+100;
    LL arr[N],p,q;
    multiset<LL>ms;
    multiset<LL>::iterator it;
    //代替scanf,速度更快,俗称输入挂
    LL mcin() {
      char ch=' ';
      LL ans=0;
      while(ch<'0' || ch>'9')
        ch=getchar();
      while(ch<='9' && ch>='0') {
        ans=ans*10+ch-'0';
        ch=getchar();
      }
      return ans;
    }
    //代替printf,速度更快,俗称输出挂
    void mout(LL x) {
      if(x > 9) {
        mout(x/10);
      }
      putchar(x%10 + '0');
    }
    int main() {
    
      LL n,k,x,y;
      LL sum1,sum2=0,cnt;
    //  freopen("in.txt","r",stdin);
    //  freopen("out.txt","w",stdout);
      n=mcin(),k=mcin();
      sum1=sum2=0;
      p=q=0;
      for(int i=1; i<=n; i++) {
        x=mcin();
        if(x==1) {
          y=mcin();
          arr[++q]=y;
          ms.insert(y);
          if(q==1)p=1;
          sum1+=y;
          sum2+=y*y;
          if(q-p+1>k) {
            sum1-=arr[p];
            sum2-=arr[p]*arr[p];
            it=ms.find(arr[p]);
            ms.erase(it);
            p++;
          }
        } else if(x==2) {
          printf("%.2lf\n",(LL)(sum1/min(k,q-p+1))*1.0);
        } else if(x==3) {
          printf("%.2lf\n",1.0*sum2/min(k,q-p+1)-
                 (1.0*sum1/min(k,q-p+1))*(1.0*sum1/min(k,q-p+1)));
        } else {
          cnt=0;
          if(ms.size()==1) {
            printf("%.2lf\n",*(ms.begin())*1.0);
            continue;
          }
          for(it=ms.begin(); it!=ms.end(); it++) {
            if(++cnt==min(k,q-p+1)/2) {
              break;
            }
          }
          if(min(k,q-p+1)&1) {
            printf("%.2lf\n",(*(++it))*1.0);
          } else {
            printf("%.2lf\n",1.0*((*it)+(*(++it)))/2);
          }
        }
      }
      return 0;
    
    }

    代码实现(线段树):

    #include<iostream>
    #include<string.h>
    #include<stdio.h>
    #include<cmath>
    #include<set>
    #include<algorithm>
    #define LL long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N=2e2+100;
    const int M=2e6+100;
    int arr[M],p,q;
    int Left[N],Right[N],dat[N];
    void build(int p,int l,int r) {
      Left[p]=l;
      Right[p]=r;
      if(l==r) {
        dat[l]=0;
        return ;
      }
      int mid=(l+r)/2;
      build(2*p,l,mid);
      build(2*p+1,mid+1,r);
    }
    void change(int p,int x,int v) {
    
      if(Left[p]==Right[p]) {
        dat[p]+=v;
        return ;
      }
      int mid=(Left[p]+Right[p])/2;
      if(x<=mid) {
        change(2*p,x,v);
      } else {
        change(2*p+1,x,v);
      }
      dat[p]=dat[p*2]+dat[2*p+1];
    }
    int query(int p,int x) {
    
      /*if(dat[p]<x)return -1;
      题目保证每次查询必有解 */
      if(Left[p]==Right[p]) {
        return Left[p];
      }
      if(dat[p*2]>=x) {
        return query(2*p,x);
      } else {
        return query(2*p+1,x-dat[2*p]);
      }
    }
    int main() {
    
      int n,k,x,y;
      int sum1,sum2=0,tmp,mid;
      while(scanf("%d%d",&n,&k)!=EOF) {
        memset(dat,0,sizeof(dat));
        sum1=sum2=0;
        p=q=0;
        build(1,1,100);
        for(int i=1; i<=n; i++) {
          scanf("%d",&x);
          if(x==1) {
            scanf("%d",&y);
            arr[++q]=y;
            change(1,y+1,1);
            if(q==1)p=1;
            sum1+=y;
            sum2+=y*y;
            if(q-p+1>k) {
              sum1-=arr[p];
              sum2-=arr[p]*arr[p];
              change(1,arr[p]+1,-1);
              p++;
            }
          } else if(x==2) {
            printf("%.2lf\n",(int)(sum1/min(k,q-p+1))*1.0);
          } else if(x==3) {
            printf("%.2lf\n",1.0*sum2/min(k,q-p+1)-
                   (1.0*sum1/min(k,q-p+1))*(1.0*sum1/min(k,q-p+1)));
          } else {
            tmp=min(k,q-p+1);
            if( tmp & 1 ) {
              printf("%.2lf\n",1.0*query(1,tmp/2+1)-1.0);
            } else {
              printf("%.2lf\n",1.0*(1.0*query(1,tmp/2+1)+
                  1.0*query(1,tmp/2)-2.0)/2);
            }
          }
        }
      }
      return 0;
    
    }

     

    展开全文
  • 算法--区间数据计算

    2013-07-13 12:13:00
    从一堆数据中查询出每个区间的起始数据,结束数据以及数据个,同时可以设置相应精度(小数位数)。 区间数据数据结构 1、区间数据主要包括当前区间的起始数据,结束数据以及数据个。结构如下: public ...

    最近一年多来,一直比较忙,最近一段时间终于空闲了,把以前没写的都补上.....

    这边随笔主要是计算一系列数据的间隔数据。从一堆数据中查询出每个区间的起始数据,结束数据以及数据个数,同时可以设置相应精度(小数位数)。

    区间数据数据结构

     1、区间数据主要包括当前区间的起始数据,结束数据以及数据个数。结构如下:

        public struct IntervalData<TKey, TValue>
        {
            private TKey _startValue;
            private TKey _endValue;
            private TValue _count;
    
            public IntervalData(TKey startValue, TKey endValue, TValue count)
            {
                this._startValue = startValue;
                this._endValue = endValue;
                this._count = count;
            }
    
            public TKey StartValue
            {
                get { return this._startValue; }
                set { this._startValue = value; }
            }
    
            public TKey EndValue
            {
                get { return this._endValue; }
                set { this._endValue = value; }
            }
    
            public TValue Count
            {
                get { return this._count; }
                set { this._count = value; }
            }
        }
    

    区间数据计算算法

     首先需要注意的几点如下:

    1、区间应该大于等于1,精度必须小于等于15(double精度最大值)。

    2、区间宽度需要微调,相应需要增加相对应的精度值。

    3、最大值和最小值需要微调,相应需要增加或者减少相对应的精度值。

        public class DataCalculator
        {
            public int IntervalCount { get; set; }
    
            public double IntervalWidth { get; private set; }
    
            public double MaxValue { get; set; }
    
            public double MinValue { get; private set; }
    
            public const int MAX_DIGIT_SCALE = 15;
    
            public DataCalculator()
            {
    
            }
    
            public DataCalculator(int intervalCount)
            {
                if (intervalCount <= 0)
                {
                    this.IntervalCount = 1;
                }
                else
                {
                    this.IntervalCount = intervalCount;
                }
            }
    
            /// <summary>
            /// 计算间隔数据起始点,结束点以及数量的列表。
            /// </summary>
            /// <param name="values">需要计算的数值列表。</param>
            /// <param name="digits">小数点位数。用于精确到指定位数的小数点。
            /// 大于等于0,小于等于15。小于0时设置为0,大于15时设置为15。</param>
            /// <returns>返回间隔数据列表。</returns>
            public IList<IntervalData<double, int>> Calculate(IList<double> values, int digits = 0)
            {
                if (values == null || values.Count == 0)
                {
                    return new List<IntervalData<double, int>>();
                }
    
                CheckDoubleScale(ref digits);
                AdjustMinAndMaxValue(values, digits);
                AdjustIntervalWidth(digits);
    
                return CalculateResult(values, digits);
            }
    
            private IList<IntervalData<double, int>> CalculateResult(IEnumerable<double> values, int digits)
            {
                var dataResult = new List<IntervalData<double, int>>();
                double startValue = this.MinValue;
    
                for (int index = 0; index < this.IntervalCount; index++)
                {
                    int count = 0;
                    double endValue = Math.Round(startValue + this.IntervalWidth, digits);
    
                    foreach (double currValue in values)
                    {
                        if (currValue >= startValue &&
                            currValue < endValue)
                        {
                            ++count;
                        }
                    }
    
                    if (index == this.IntervalCount - 1 && this.MaxValue < endValue)
                    {
                        this.MaxValue = endValue;
                    }
    
                    dataResult.Add(new IntervalData<double, int>(startValue, endValue, count));
                    startValue = endValue;
                }
    
                return dataResult;
            }
    
            private void AdjustIntervalWidth(int digits)
            {
                double intervalWidth = (this.MaxValue - this.MinValue) / this.IntervalCount;
                double currentIntervalWidth = Math.Round(intervalWidth, digits);
    
                if (currentIntervalWidth < intervalWidth)
                {
                    currentIntervalWidth += 1 / Math.Pow(10, digits);
                }
    
                if (currentIntervalWidth == 0)
                {
                    currentIntervalWidth = 1;
                }
    
                this.IntervalWidth = currentIntervalWidth;
            }
    
            private void AdjustMinAndMaxValue(IEnumerable<double> values, int digits)
            {
                double minValue = values.Min();
                double maxValue = values.Max();
    
                // 计算最小值,将最小值减少相应的精度值,避免最小值未进入计算
                double currentMinValue = Math.Round(minValue, digits);
    
                if (currentMinValue > minValue)
                {
                    currentMinValue -= 1 / Math.Pow(10, digits);
                }
    
                // 计算最大值,将最大值增加相应的精度值,避免最大值未进入计算
                double currentMaxValue = Math.Round(maxValue, digits);
    
                if (currentMaxValue <= maxValue)
                {
                    currentMaxValue += 1 / Math.Pow(10, digits);
                }
    
                this.MinValue = currentMinValue;
                this.MaxValue = currentMaxValue;
            }
    
            private static void CheckDoubleScale(ref int digits)
            {
                if (digits < 0)
                {
                    digits = 0;
                }
    
                if (digits > MAX_DIGIT_SCALE)
                {
                    digits = MAX_DIGIT_SCALE;
                }
            }
        }

    具体应用

    应用比较简单,示例如下:

                IList<double> dataPoints = new List<double>() { -4, 5, 6, 99.54, 0, 65 };
    
                var calculator = new DataCalculator(5);
                IList<IntervalData<double, int>> datas = calculator.Calculate(dataPoints, 2);
    
                StringBuilder builder = new StringBuilder();
    
                foreach (var data in datas)
                {
                    builder.AppendLine(string.Format("StartValue:{0}  EndValue:{1}  Count:{2}", data.StartValue, data.EndValue, data.Count));
                }
    
                string result = builder.ToString();
                Console.Write(result);

    输出结果为:

    StartValue:-4  EndValue:16.71  Count:4
    StartValue:16.71  EndValue:37.42  Count:0
    StartValue:37.42  EndValue:58.13  Count:0
    StartValue:58.13  EndValue:78.84  Count:1
    StartValue:78.84  EndValue:99.55  Count:1

    可以将该返回数据用于相关图形进行绑定以及显示。

    转载于:https://www.cnblogs.com/jasenkin/p/interval_data_calculator.html

    展开全文
  • 最大值和最小值 遍历一遍直接找到最大值或者最小值是比较...我们要解决的问题是如何同时找到一组数据中的最大值和最小值。如果直接遍历两边会进行2n次比较,但事实上可以用3/2n次比较就可以求出最大值和最小值。 不同

    最大值和最小值

    遍历一遍直接找到最大值或者最小值是比较简单的算法:

    int find_maxnumber(int* a)
    {
    	int maxa = 0;
    	for (int i = 1; i <= n; i++)
    	{
    		if (a[i] > maxa)
    		{
    			maxa = a[i];
    		}
    	}
    	return maxa;
    }
    

    我们要解决的问题是如何同时找到一组数据中的最大值和最小值。如果直接遍历两边会进行2n次比较,但事实上可以用3/2n次比较就可以求出最大值和最小值。

    不同于一次遍历一个跟最大值与最小值对比,我们每次比较的时候选择两个数据,先将两个数据对比,再将大的跟最大值比,小的跟最小值比

    双最值源代码

    #include<iostream>
    using namespace std;
    int main()
    {
    	constexpr int maxn = 200;
    	constexpr int INF = 0x3f3f3f3f;
    	int a[maxn];
    	int n, maxa = 0, mina = INF;
    	cin >> n;
    	for (int i = 1; i <= n; i++)
    	{
    		cin >> a[i];
    	}
    	for (int i = 1; i <= n - 1; i = i + 2)
    	{
    		if (i > n) break;
    		int a1 = a[i], a2 = a[i + 1];
    		if (a1 > a2)
    		{
    			if (a1 > maxa) maxa = a1;
    			if (a2 < mina) mina = a2;
    		}
    		else
    		{
    			if (a2 > maxa) maxa = a2;
    			if (a1 < mina) mina = a1;
    		}
    	}
    	if (a[n] > maxa) maxa = a[n];
    	if (a[n] < mina) mina = a[n];
    	cout << "max = " << maxa << endl;
    	cout << "min = " << mina << endl;
    	return 0;
    }
    

    输入1:

    8
    2 8 7 1 3 5 6 4

    输出1:

    max = 8
    min = 1

    输入2:

    11
    2 8 7 1 3 5 6 4 9 0 4

    输出2:

    max = 8
    min = 1

    期望为线性时间的选择算法

    我们用前面提到的快速排序的随机化改版来做到O(n)时间内求出区间第k大。

    (点击复习随机化快速排序)

    与快速排序一样,我们仍然将输入数据进行划分。但与快速排序不同的是,快速排序会递归处理划分的两边,而randomized_select只处理划分的一边。这一差异会在性能分析中体现出来:快速排序的期望时间为O(lgn),而randomized_select的期望运行时间为O(n)。

    randomized_select核心函数

    int randomized_select(int* a, int l, int r, int i)
    {
    	if (l == r)
    	{
    		return a[l];
    	}
    	int q = randomized_partition(a, l, r);
    	int k = q - l + 1;
    	if (i == k)
    		return a[q];
    	else if (i < k)
    		return randomized_select(a, l, q - 1, i);
    	else
    		return randomized_select(a, q + 1, r, i - k);
    }
    

    区间第k大源代码

    //区间第k大
    #include<iostream>
    #include<time.h>
    #include<stdlib.h>
    using namespace std;
    inline int ls(int x) { return x << 1; }
    inline int rs(int x) { return x << 1 | 1; }
    inline int father(int x) { return x >> 1; }
    constexpr int maxn = 200;
    constexpr int inf = 0x3f3f3f3f;
    int n, N;
    int a[maxn];
    int randomized_partition(int* a, int l, int r);
    int partition(int* a, int l, int r);
    int randomized_select(int* a, int l, int r, int i)
    {
    	if (l == r)
    	{
    		return a[l];
    	}
    	int q = randomized_partition(a, l, r);
    	int k = q - l + 1;
    	if (i == k)
    		return a[q];
    	else if (i < k)
    		return randomized_select(a, l, q - 1, i);
    	else
    		return randomized_select(a, q + 1, r, i - k);
    }
    int randomized_partition(int* a, int l, int r)
    {
    	srand((unsigned)time(NULL));
    	int i = (rand() % (r - l)) + l;
    	int resj = a[i];
    	a[i] = a[r];
    	a[r] = resj;
    	return partition(a, l, r);
    }
    int partition(int* a, int l, int r)
    {
    	int x = a[r];
    	int i = l - 1;
    	for (int j = l; j <= r - 1; j++)
    	{
    		if (a[j] <= x)
    		{
    			i++;
    			int res = a[j];
    			a[j] = a[i];
    			a[i] = res;
    		}
    	}
    	int ret = i + 1;
    	int res = a[r];
    	a[r] = a[ret];
    	a[ret] = res;
    	return ret;
    }
    int main()
    {
    	int n, k;
    	cin >> n;
    	for (int i = 1; i <= n; i++)
    	{
    		cin >> a[i];
    	}
    	cin >> k;
    	int ans = randomized_select(a, 1, n, k);
    	cout << ans << endl;
    	return 0;
    }
    

    排序后数列:

    0 0 2 2 3 3 3 5

    输入1:

    8
    2 5 3 0 2 3 0 3
    4

    输出1:

    2

    输入2:

    8
    2 5 3 0 2 3 0 3
    5

    输出2:

    3

    展开全文
  • 中位数计算

    千次阅读 2016-09-29 18:24:07
    下载测试数据文件(1百万条数据中位数为49899),选择不同的区间大小(width),考察计算结果与真实中位数的误差。公式代码实现matlabclear all; clc;N = 1000000; width = 100; [a] = textread('rand1m.txt','%d'...

    题目


    中位数计算。选择你熟悉的编程语言实现教材P31上公式(2.3)的算法,用于估算大量数据的中位数。下载测试数据文件(1百万条数据,中位数为49899),选择不同的区间大小(width),考察计算结果与真实中位数的误差。

    公式


    数据挖掘 中位数计算

    代码实现


    matlab

    clear all;
    clc;
    
    N = 1000000;
    width = 100;    %区间长度
    [a] = textread('rand1m.txt','%d');
    %此处可直接使用median(a)求出中位数49899
    
    max = max(a);       %用其他语言的话,最值可用冒泡排序求出
    min = min(a);
    num = (max - min) / width;
    num = round(num);       %向上取整
    count = zeros(num,1);   %保存各区间的个数
    
    %计for i = 1:N
        count(floor((a(i)-min)/width+1)) = count(floor((a(i)-min)/width+1)) + 1;
    end
    
    %确定中位数所在的区间位置index
    %计算该区间以前的频数和sigma
    sigma = 0;
    index = 1;
    while N/2-sigma>0
        sigma = sigma + count(index);
        index = index +1;  
    end
    index = index -1;
    sigma = sigma - count(index);
    
    %根据公式计算中位数
    L1 = min + width*(index-1);
    median = L1 +((N/2-sigma)/count(index)) * width;
    median = fix(median);
    

    C

    #include<stdio.h>
    const int width=100;    //区间长度
    void main(){
        FILE *fp1,*fp2;
        int a,max=2000,min=2000,N=0,median;
        if( (fp1 = fopen("rand1m.txt","r"))==NULL ) 
            printf("error");
    
        //取出最大值与最小值
        while(fscanf(fp1,"%d%*[^0-9]",&a)>0){
            if(a>=max)
                max = a;
            if(a<=min)
                min = a;
            N++;
        }
        fclose(fp1);
    
        int num = (max - min) / width +1;   //区间个数
        int* count = new int[num];      //区间频数
        for(int i=0; i<num; ++i)
            count[i]=0;
    
        if( (fp2 = fopen("rand1m.txt","r"))==NULL ) 
            printf("error");
    
        //计数
        while(fscanf(fp2,"%d%*[^0-9]",&a)>0){
            count[(a-min)/width]++;
        }
        fclose(fp2);
    
        //确定区间index 统计index前所有区间频数和sigma
        int sigma = 0;
        int index = 0;
        while(N/2 - sigma >0){
            sigma += count[index];
            index ++;
        }
        index --;
        sigma -= count[index];
    
        //套用公式
        int L1 = min + width*index;     //区间下限
        double rate = (1.0) * (N/2-sigma) / count[index];
        median = L1 + rate * width;
    
        printf("L1=%d\nmedian=%d\n",L1,median);
    
    }
    
    展开全文
  • 求给定区间 [X,Y] 满足下列条件的整数个:这个恰好等于 K 个互不相等的 B 的整数次幂之和。 输入格式 第一行包含两个整数 X 和 Y,接下来两行包含整数 K 和 B。 输出格式 只包含一个整数,表示满足条件的的...
  • 给定一个 111 ~ nnn 的排列,求以 bbb 为中位数的 连续子序列且长度为奇数 的个数。 显然这段序列包含 bbb. 中位数的定义:排序后在最中间的数。 算法一 对于 30%30 \%30% 的数据,n≤100n \leq 100n≤100. 由于这...
  • 求给定区间[X,Y]满足下列条件的整数个:这个恰好等于K个互不相等的BB的整数次幂之和。 例如,设X=15,Y=20,K=2,B=2,则有且仅有下列三个满足题意: 17=2^4+2^0 18=2^4+2^1 20=2^4+2^2 输入格式 第一行包...
  • find函数和distance函数都是算法库里的函数 ,包含在头文件algorithm, 算是STL的内容 只介绍最简单的用法: find函数有三个参数, 分别代表(起点, 终点后一, 要找的) 返回一个地址,可以是容器, 或者数组 如果...
  • 数位DP

    2019-09-23 23:56:40
    问题:求某个区间[L,R]满足某种限制条件的的个数。 暴力的思路:我们可以枚举[L,R]区间内部所有的,依次判断每个是否合法,若合法,就记下。 显然,如果数据范围较大,达到1018甚至更大的级别的时候,这种...
  • 二分查找的思想是在已经排序(升序)的数组中,如果要查找的数比中位数小,那么其位置只可能在左半部分,相反只能在右半部分。这样每次把查找区间缩小一半,比顺序查找效率快得多。 非递归写法: public static int...
  • 数位dp详解

    2017-07-09 11:37:06
    一般思路就是把区间所有的数字都枚举一遍,逐个判断是否满足题意,但这类题目往往具有庞大的数据规模,比如有的题目所给的区间是【1, 10 ^20】,暴力枚举肯定超时,这就要求我们寻找一种更高效的算法,这便有了数位DP
  • 1.二进制1的个数题目要求: 给定一个长度为n的数列,请你求出数列每个的二进制表示1的个数。 输入格式 ...运算的两个基本算法: 1.求n的第k数字: n >> k & 1 2.返回x的最后一
  • 从1-1000猜一个数字,这时第一一般会猜500(不搞事的话),因为通常对半分是最快猜中数字的方法,也就是二分法。来吧来吧!今天我们来讲讲二分法。二分法是数学领域的概念,经常用于计算机的查找过程。定义:...
  • 前缀算法

    千次阅读 2012-10-21 23:33:51
    前缀算法能够从一个给定数据空间找出其前缀特征,即前缀集合。前缀集合具有确定性,能够匹配该前缀集合的数据一定...算法的输入是n二进制数区间的起始值a1a2...an和结束值b1b2...bn,二进制的左边是高位,右边
  • 算法复习1 堆

    2018-11-09 15:47:12
    insert() 函数有以下三种用法:  1、在指定位置loc前插入值为val的元素,返回指向这个元素的迭代器 2、在指定位置loc前插入num个值为val的元素  ...如果从数据流中读出偶数个数值,那么中位数就...
  • 在选择排序,需要遍历无序区间,找到无序区间的最小数据,然后放入有序区间的末尾。但是在插入排序需要将a[i],(i 之前是有序区间),在有序区间中找到合适的位置并且插入。详细操作如下 定义a[0]…..到 a[n-1] ...
  • 从第1个特征到第k个特征,每次选择一个特征,找出该特征取值的中位数,以此特征的中位数划分超平面,每次划分都是在之前划分的基础进行的,也就是在上次划分的每个子区间选择下一特征进行划分,当特征用完了,则重新...
  • 一致性hash算法

    2020-07-20 19:03:47
    1. 一致性hash算法介绍 一致性哈希算法在1997年由麻省理工学院提出,是一种特殊的哈希算法,目的是解决分布式缓存的问题。在移除或者添加一个服务器时,...hash取值区间: 816进制 共有 2^32种可能性!!! (24)8=2^3
  • 3.2.3 位置度量:均值和中位数 61 3.2.4 散布度量:极差和方差 62 3.2.5 多元汇总统计 63 3.2.6 汇总数据的其他方法 64 3.3 可视化 64 3.3.1 可视化的动机 64 3.3.2 一般概念 65 3.3.3 技术 67 3.3.4 可视...
  • 排序算法之快速排序

    2019-05-21 08:45:32
    定义:快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据...选取区间中第一个作为基准,取区间第一为le...
  • 算法导论中文版

    2016-10-26 10:13:58
    第9章 中位数和顺序统计量  9.1 最小值和最大值  9.2 期望为线性时间的选择算法  9.3 最坏情况为线性时间的选择算法  思考题  本章注记 第三部分 数据结构 第10章 基本数据结构  10.1 栈和队列  10.2...
  • 常用算法代码

    2017-09-11 11:26:53
    | 所有数位相加 25 Number 数论 26 1 |递推求欧拉函数 PHI(I) 26 |单独求欧拉函数 PHI(X) 26 | GCD 最大公约数 26 | 快速 GCD 26 | 扩展 GCD 26 | 模线性方程 A * X = B (% N) 26 | 模线性方程组 26 | ...
  • 如上图所示,在一个黑色的大区间内,只有几个红色的数据对我们来说是有用的,所以我们可以将这些红色的数据从大区间中抽出来,组成一个新的序列,新序列的下标原序列的位置。新序列的值原序列的相应位置的值。...
  • 算法实现:对n个数据,比较n-1趟,在每趟区间中将最小下标记录在k,若k不为1,将b[1]与b[k]交换,始终保持剩余元素的第一个为该趟最小值,实现由小到大的排序。 3.插入排序原理:将原序列逐个分开,每次比较...
  • 全书内容分为11章,包括程序设计入门、循环结构程序设计、数组和字符串、函数和递归、基础题目选解、数据结构基础、暴力求解法、高效算法设计、动态规划初步、数学概念与方法、图论模型与算法,覆盖了算法竞赛入门所...
  • 几种常见排序 基于比较的排序算法: 下界是 nlgn 1.1 SelectionSort:每次选出最下的元素,放在当前循环... 先将数据区间分为n个桶,把数据分放到对应的桶;对桶内的数据采用插入排序;再把各个桶的排序结果串起来。
  • 前言由于计算机编程语言数据类型存储的限制,无法使用内置的数据类型来进行任意数字的计算,其中任意整数四则运算的除法最难处理。因此,大整数除法成了很多高校数据结构课程的课程设计作业。今天为大家带来...

空空如也

空空如也

1 2 3 4 5
收藏数 87
精华内容 34
关键字:

区间数据中位数算法