面试有两道笔试题没写出来,请多多各位帮帮忙
题目一:一个数组,“支配者”是在数组中出现频率超过一半的整数, 例如[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的类库,并且要尽可能降低时间复杂度,在规定的时间内没想出一个好办法,笔试也就没通过了,所以请教一下大家怎么样才能做出来?谢谢各位!
题目一:一个数组,“支配者”是在数组中出现频率超过一半的整数, 例如[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的类库,并且要尽可能降低时间复杂度,在规定的时间内没想出一个好办法,笔试也就没通过了,所以请教一下大家怎么样才能做出来?谢谢各位!
自己建立一个类,包括属性:value,count,pos(数组)。
然后把查询后的结果,即所有生成的类对象放在一个数组里,搞定。
第二题:
从两边往中间找,有点类似于数据结构中的某种排序方法,不过这是寻找。
1.随便从一边开始,然后比较两端,记下小的一端,从大的一端往里找。
2.如果碰到了比小的一端还小的数据,则记下它,从以前的小的一端开始往里找。
3.一直这样下去。
自己建立一个类,包括属性: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个
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("没有支配者");
}}
用了另一个数组存储,不知有没有更好的方法?