刚刚讯雷的一个笔试题
一共五题，就说有意思的这一题
题目大概是：有数组int []d={1,2,-5,6,等等};
删除其中等于10的元素并返回删除的个数，要求时间和空间做优化，要先想思路
题目是c的,其实用java也一样

数组中，删除一个数则会令删除这个数后面的数都向前移，如果有10W个数，则要移10W-1，如果我们减少移动的次数，或者只移一个数，那么效率将会得到提高
我的做法是设定查找的左右界限
int l=0,r=数组长度-1;
int count;//删除的个数
while(l<r){
while(l<r&&d[r]==10){
r--;
count++;
}
while(l<r&&d[l]!=10)l++;
if(l<r){
d[l]^=d[r];//交换值
d[r]^=d[l];
d[l]^=d[r];
l++;r--;count++;
}
}
return count;
不知道还有什么更好的方法

机试悲剧呀，忘记二个函数了，又上不了网查～
哎，让我明天等通知，然后又加上一句，如果没通知不要来。桌子上呀，都是杯子呀～～～
找工作，应届生，在深圳南山，先做实习生也行，攒钱买电脑了
【工作经历详细介绍】
以下是学校做过的一些主要项目开发：
猜数字游戏（C）模猜数字游戏的各个功能实现。
迷宫游戏(C)迷宫的随机生成和最佳路径的寻找
通讯录(vc6.0+access)和(java+mysql)仿QQ通讯录，联系人添加，修改，删除，消息的收发。
计算器（HTML javascript）,模拟计算器组合要给你实现。
俄罗斯方块(java)，实现俄罗斯方块各种功能，支持扩展高级功能。
即时聊天工具（java）仿QQ，Socket,多线程技术，p2p。
mp3播放器(java 非jmf)仿千千静听，解析和使用千千静听皮肤，实现在线查找和下载mp3。
数学公式分析器(java netbean)高级科学计算表达式的计算，纠正大部分表达式。
企业员工资料管理系统（java netbean,ms sql2000)对员工信息及工资的添加、删除、修改、查询。
基于B2B的网上批发交易系统（asp.net C# + sql server）,主要实现发布出售或收购商品信息，可以展显商品；通过该系统以方便、有效的进行批发物品的交易等的管理。
在线音乐网（asp.net C# + sql server 2k）实现文件的上传，媒体的播放，商品的卖出，网站和数据库管理方便。
B2B在线交易批发网（毕设asp.net C# + sql server 2k）兼容b2c,c2c，可以实现在线商品的交易和讯息的发布。
在线聊天室（JAVA）,主要实现在线聊天功能，主要运用Socket,多线程技术,自定义聊天室通讯协议。
QQ找茬测试版（JAVA，jni,屏幕截图）,主要完成了自动找茬功能。
【技能专长】
1.精通java以及SQL SERVER数据库,熟悉c++,html,asp.net等编程语言
2.熟练掌握应用powerdesigne ，netbeans，Visual Studio 2008,Dreamweaver等工具
3.了解Thread、Socket、JDBC等J2EE核心技术
4.熟悉AWT,Swing等包的使用
5.较强的逻辑和分析能力

[解决办法]
你那样效率不高呀，
可不可以用改进和二分法来实现，并记下删除的次数
[解决办法]

Java code

    public static void main(String[] args) {        int [] a={2,1,2,-5,6,10,34,9,10,10,33};        int count=0;        ArrayList<Integer> my=new ArrayList<Integer> ()    ;        for (int i = 0; i <a.length; i++) {            my.add(a[i]);        }                while((boolean) my.remove((Object)10)){            count++;                    }        System.out.println(count);    }
[解决办法]
C/C++ code
#include <stdio.h>int main(int argc, char *argv[]){    int a[]={2,1,2,-5,6,10,34,9,10,10,33};    int count = 0;    int b = sizeof(a)/sizeof(int);    int *p = a;    int *pp = &a[b];        int i = 0;    while(i < b)    {        if (a[i] == 10)        {            a[i] = *p;            p++;            count++;        }        i++;    }        printf("count:%d\n", count);    while(p < pp)    {        printf("%d ", *p);        p++;    }        return 0;}
[解决办法]
C/C++ code
int TrimNum(int arr[], int len, int num){    int total = 0, index = 0;        while (index < len)    {        if (arr[index] == num)        {            totoal++;            continue;        }        if (total > 0)            arr[index - total] = arr[index];        index++;    }    return total;} 
 
[解决办法]
1.这个本质应该是以10为flag元素做的一次快速排序划分
划分完成后返回划分小于10的前半部分就行了
2.或者枚举每一个元素，如果大于等于10
就与数组中的最后一个小于10的元素交换
有点迷糊，不清楚1和2是不是一个逻辑
快排忘得差不多了。。。
[解决办法]
如果只是删除数组的元素,不要求删除了保持原来的顺序的话
我们只要删除是10的元素,然后判断数组的最后一个元素是不是10,是10继续删除 数组-1,继续判断...
不是10的话,直接赋值到删除的位置,数组-1
[解决办法]
楼主学的这么多，找工作还不是很容易，我这样以后该怎样啊!!迷茫！！！！！！！
[解决办法]
探讨

Java code
    public static void main(String[] args) {
        int [] a={2,1,2,-5,6,10,34,9,10,10,33};
        int count=0;
        ArrayList<Integer> my=new ArrayList<Integer> ()    ;
        fo……

[解决办法]
我觉得如果要把未删除的向前移动的话那就从后面开始扫描，找到了的话就跟末尾的作交换，删除一个之后末尾指针向前移一位，最后按长度截断数组就可以了。排序肯定会多费时间的。没有说要往前移动的话就随便从哪头开始都不成问题。如果你每找到一个都把它后面所有的数都往前面移动一格就有问题了。人家又没要求排序后才输出。

这样的话比较次数还是线性的，临时空间也是0.



[解决办法]
探讨

1.这个本质应该是以10为flag元素做的一次快速排序划分
划分完成后返回划分小于10的前半部分就行了
2.或者枚举每一个元素，如果大于等于10
就与数组中的最后一个小于10的元素交换
有点迷糊，不清楚1和2是不是一个逻辑
快排忘得差不多了。。。

[解决办法]
给楼主个建议。


在简历中出现“精通”2个字的时候要慎重。无论自己实力如何。
[解决办法]
我给个思路.

用两个指针P和Q.从数组头元素开始

1.P指向下一个10的数字
2.Q从MAX(P,当前位置)开始查找下一个非10数字.
3.交换P,Q值
4.重复1-3,直到P或Q任意到数组尾
5.删除(P,Q]区间所有数据

效率不高.类似冒泡排序

[解决办法]
题目只要求删除数组为10的元素，在时间和空间优化，并没有要求数组的顺序保挂不变，据以我觉得这样做也可以，代码如下
int[] ar=new int[]{10,10,1,10,10,10,10,10,10,10,2,10,1};
int count=0;
int length=ar.length;
for(int i=0;i<length-count;i++){
if(ar[i]==10){
count++;

while(ar[length-count]==10){
count++;
if(i==length-count) break;
}
if(i==length-count) break;
ar[i]+=ar[length-count];
ar[length-count]=ar[i]-ar[length-count];
ar[i]=ar[i]-ar[length-count];
}
}
System.out.println(count);
//打印出不是10的所有数
for(int i=0;i<length-count;i++){
System.out.println(ar[i]);
}

有兴趣的朋友不防试试，讨论个更好的方法，是用JAVA语言实现的。这个解决方案在时间上，for+while的执行次数在length的长度相当，在空间上，只是定义了length和count变量
[解决办法]
呵呵，仔细一看，楼主的做法和我的大体思路思路差不多，虽然实现方法差距很大，但通过我的测试，如果操作的是一个数组，楼主方法的结果和我方法的结果竟然完全一样。
[解决办法]
好像，在中国处于学生毕业阶段的，能精通这些的，还没有这么牛的人吧？
别人一看简历，直接咔嚓掉。
不要轻易说精通两个字，还没学会开拖拉机，就学会开飞机了？
[解决办法]
楼主乐不起啊
[解决办法]
根据指定的数字划分,将指定的数全部划分到数字的右边
Java code
class ArrayPar{    private long[] theArray;    private int nElems;    public ArrayPar(int max){        theArray = new long[max];        nElems = 0;    }    public void insert(long value){        theArray[nElems] = value;        nElems ++;    }    public int size(){        return nElems;    }        public void dispaly(){        System.out.print("A=");        for (int j = 0; j < nElems; j++) {            System.out.print(theArray[j]+" ");        }        System.out.println("");    }        public int partitionIt(int left,int right,long pivot){        int leftPtr = left -1 ;        int rightPtr = right +1 ;        while(true){            while(leftPtr<right&&theArray[++leftPtr]!=pivot);                        while(rightPtr > left&& theArray[--rightPtr]==pivot);                        if(leftPtr>=rightPtr)                break;            else                swap(rightPtr,leftPtr);        }        return leftPtr;    }    public void swap(int dex1,int dex2){        long temp;        temp=theArray[dex1];        theArray[dex1] = theArray[dex2];        theArray[dex2] = temp;    }}public class Partition {    public static void main(String[] args) {        int maxSize = 1000;        ArrayPar arr;        arr = new ArrayPar(maxSize);        for (int j = 0; j < maxSize; j++) {            long n = (int)(Math.random()*20);            arr.insert(n);        }        arr.dispaly();        long pivot = 10;        System.out.println("划分数: "+ pivot);        int size = arr.size();        int partDex = arr.partitionIt(0, size-1, pivot);        arr.dispaly();    }} 
 
[解决办法]
最快的莫过于使用快速排序方法来遍历了。如果需要简单的话还可以使用正则表达式来匹配的哈。反正方法很多