面试有两道笔试题没写出来,请多多各位帮帮忙
题目一:一个数组,“支配者”是在数组中出现频率超过一半的整数, 例如[3,4,3,2,-1,3,3,3]数值“3”出现过5次,5除以8大于0.5 所以数值“3”是一个支配者; 而在这个数组中的支配者出现在数组下标[0,2,4,6,7]
写一个函数,在给定的整数数组中找出支配者所在的任意一个数组下标,如果一个数组中没有支配者返回-1。题目二:“有序数组中绝对值不同的数的个数”指的是,一个已经排好序的整数数组中,绝对值不相同的数字的个数。例如:[-5,-3,-1,0,3,6].请返回给定有序数组中绝对值不同的数的个数。
第一道题我当时用map做,第二道题用set做,都做出来了,但是考官要求不能用JAVA的类库,并且要尽可能降低时间复杂度,在规定的时间内没想出一个好办法,笔试也就没通过了,所以请教一下大家怎么样才能做出来?谢谢各位!

解决方案 »

  1.   

    第一题:
      自己建立一个类,包括属性:value,count,pos(数组)。
      然后把查询后的结果,即所有生成的类对象放在一个数组里,搞定。
    第二题:
      从两边往中间找,有点类似于数据结构中的某种排序方法,不过这是寻找。
      1.随便从一边开始,然后比较两端,记下小的一端,从大的一端往里找。
      2.如果碰到了比小的一端还小的数据,则记下它,从以前的小的一端开始往里找。
      3.一直这样下去。
      

  2.   

    第一题: 
      自己建立一个类,包括属性:value,count,pos(数组)。
      pos数组存放每个value的位置。
      把所有数据全部查询一遍,碰到一个新的数就给这个数生成一个对象,以后碰到同样的数则把他的位置放在pos数组里。
      查询后的结果是在一个数组里的。 
    第二题: 
      从两边往中间找,有点类似于数据结构中的某种排序方法,不过这是寻找。 
      1.随便从一边开始,然后比较两端的绝对值,记下小的一端,从大的一端往里找。 
      2.如果碰到了比小的一端还小的数据,则记下它,从以前的小的一端开始往里找。 
      3.一直这样下去。
    如:-5,-3,-2,0,2,3,4
    假如从左边开始:
    -5 4  小的:4
    4 -3  小的:-3  
    -3 3  小的:-3  (3重复一次)
    -3 2  小的:2   
    2 -2  小的:2 (2重复一次)
    0   完毕
    于是绝对值不重复的有:3个
      

  3.   


    package test;import java.util.Arrays;public class Testint { public static void main(String[] args) {
    int count = 0;
    int[] arrays = new int[] { 3, 4, 3, 2, -1, 3, 3, 3 };
    int[] flag = new int[arrays.length];
    for (int i = 0; i < arrays.length; i++) {
    flag[i] = arrays[i];
    }
    Arrays.sort(flag);// /排序
    int temp = flag[(flag.length + 1) / 2]; for (int i = 0; i < flag.length; i++) {
    if (flag[i] == temp) {
    count++;
    }
    }
    if ((double) count / flag.length > 0.5) {
    System.out.println(temp + "是支配者");
    System.out.println("下标是");
    for (int i = 0; i < arrays.length; i++)
    if (arrays[i] == temp)
    System.out.print(i);
    } else
    System.out.println("没有支配者");
    }}
    用了另一个数组存储,不知有没有更好的方法?