您的位置:澳门新葡萄京娱乐网站 > 编程知识 > 【IT笔试面试题整理】数组中现身次数超过六分之

【IT笔试面试题整理】数组中现身次数超过六分之

2019-12-22 01:31

1、定义一个新数组arr,遍历数组给arr赋值,arr[元素]=现身的次数2.排序下arr,取第多少个的key和value,key是指标成分,value是现身次数,验证下后归来3.光阴复杂度是O 空间上会新创制个数组

06 第四种解法

选择双指南针。依然先将数据排序,定义左右七个指针,分别从0起先,如果左右指南针相等,表达是循环的第三回依旧另行了,就须求将右指针以后移动壹个人。假诺左指针所指向成分加上k后十三分右指针的要素,那么次数加1,接着要一口咬住不放,假设右指针所指向地方后边的因素和当下因素相等,那么右指针继续以后运动。如果左指针所指向成分加上k后小于右指针的元素,表达左边的因素小了,左指针向前挪动。如若左指针所指向成分加上k后胜出右指针的要素,表达侧边的成分小了,右指针向前挪动。

此解法的岁月复杂度是O,空间复杂度是O。

public int findPairs5(int[] nums, int k) { if (nums == null || nums.length == 0 || k < 0) { return 0; } Arrays.sort; int count = 0; int start = 0, end = 0; while (end < nums.length) { if (start == end) { end  ; } else if (nums[start]   k == nums[end]) { count  ; while (end   1 < nums.length && nums[end] == nums[end   1]) { end  ; } end  ; } else if (nums[start]   k < nums[end]) { start  ; } else if (nums[start]   k > nums[end]) { end  ; } } return count;}

 思路1:
  
  创建两个hash_map,key为数组中的数,value为此数现身的次数。遍历一遍数组,用hash_map总括每种数出现的次数,并用四个值存款和储蓄目后面世次数最多的数和对应现身的次数。
  
  那样能够做到O(n卡塔尔的时日复杂度和O(n卡塔尔国的半空中复杂度,满意标题标渴求。
  
  不过未有运用“二个数现身的次数超过了概略上”那脾个性。大概算法还可能有拉长的空中。
  
 思路2:      使用八个变量A和B,当中A存款和储蓄有个别数组中的数,B用来计数。开始时将B伊始化为0。
  
  遍历数组,借使B=0,则令A等于当前数,令B等于1;纵然当前数与A相通,则B=B 1;假若当前数与A不一样,则令B=B-1。遍历结束时,A中的数正是要找的数。
  
  这些算法的时日复杂度是O(n卡塔尔(英语:State of Qatar),空间复杂度为O(1卡塔尔(قطر‎。

数组中有五个数字现身的次数超过数首席营业官度的八分之四,请寻找这些数字。比如输入多个长短为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中现身了5次,超过数经理度的二分之一,由此输出2。若是不真实则输出0。

04 第三种解法

对此第二种解法,仍可以将剖断放在循环体里面。

public int findPairs3(int[] nums, int k) { if (nums == null || nums.length == 0 || k < 0) { return 0; } Map<Integer,Integer> map = new HashMap<Integer,Integer>(); for (int n : nums) { map.put(n, map.getOrDefault; } int count = 0; for (Map.Entry<Integer, Integer> entry : map.entrySet { if  { if (entry.getValue() >= 2) { count  ; } } else { if (map.containsKey(entry.getKey { count  ; } } } return count; }
 1 int findMoreThanHalf(int[] arr) {
 2         if (null == arr) 
 3             return -1;
 4 
 5         int nValue = arr[0];
 6         int count = 1;
 7         for (int i = 1; i < arr.length; i  ) {
 8             if (nValue == arr[i]) {
 9                 count  ;
10             } else {
11                 if (count == 0) {
12                     nValue = arr[i];
13                     count = 1;
14                 }
15                 count--;
16             }
17         }
18         return nValue;
19     }
e,count=1for i=1;iarr.length return e

以上就是本次的全部内容和代码,感谢大家对脚本之家的支持。

那是悦乐书的第254次更新,第267篇原创

【参照他事他说加以考察代码】

1、定义变量e代表现身次数最多的因素,变量count用于判别现身次数用2.遍历数组,当前因素与e相比较,相似的count ,不相同的count--,count为0时当前因素覆盖e3.遍历数组验证e所现身的次数有未有凌驾二分一4.时刻复杂度O

05 第多种解法

利用HashSet。使用四个HashSet,雷同分为三种状态:k等于0和K不等于0。

若是k等于0时,对数组实行遍历,如若当前成分不设有于set1中,就增加进set1,借使存在set1中,就去看清是不是留存于set第22中学,假使不设有,次数就加1,并将成分增加进set第22中学。

借使k不等于0,遍历数组,将前段时间因素加多进set1,将眼下成分加上k后再增加进set2,然后使用retainAll方法,将set1中不带有set2要素的要素剔除掉(也正是两set的混合),最终count等于set1七月素的个数。

public int findPairs4(int[] nums, int k) { if (nums == null || nums.length == 0 || k < 0) { return 0; } Set<Integer> set1 = new HashSet<Integer>(); Set<Integer> set2 = new HashSet<Integer>(); int count = 0; if  { for (int n : nums) { if (!set1.contains { set1.add; } else { if (!set2.contains{ count  ; } set2.add; } } } else { for (int n : nums) { set1.add; set2.add; } set1.retainAll; count = set1.size(); } return count;}

 

02 第意气风发种解法

暴力解法。先排序,然后选拔两层循环,总计分化因素的断然值,若是等于k,次数就加1。在外围第意气风发层循环这里,就算前后成分相仿,就跳过当前巡回,进行下一次巡回。在内层循环这里同样做了就像的判断,消除再一次总计。

此解法的小时复杂度是O,空间复杂度是O。

public int findPairs(int[] nums, int k) { if (nums == null || nums.length == 0 || k < 0) { return 0; } Arrays.sort; int count = 0; for (int i=0; i<nums.length; i  ) { int n = nums[i]; if (i >= 1 && nums[i-1] == nums[i]) { continue; } for (int j=i 1; j<nums.length; j  ) { if (j >= i 2 && nums[j-1] == nums[j]) { continue; } if (Math.abs(n - nums[j]) == k) { count  ; } } } return count;}

【试题解析】时间复杂度O(n卡塔尔,空间复杂度O(1卡塔尔

07 小结

此题的测量检验用例中,k现身了负值,所以在极其规意况判别中,还索要剖断k小于0,那也是主旨不步步为营的三个地点。

算法专项论题最近已日更超越7个月,算法题文章121 篇,公众号对话框回复【数据布局与算法】、【算法】、【数据布局】中的任后生可畏关键词,获取体系作品合集。

上述正是全体内容,如若我们有哪些好的解法思路、建议依然其余标题,能够下方留言沟通,点赞、留言、转载正是对自身最大的报恩和支撑!

【试题描述】数组中有二个数字现身的次数超越数董事长度的八分之四,请搜索这几个数字。

01 看题和准备

今天牵线的是LeetCode算法题中Easy等级的第121题。给定三个整数数组和三个整数k,您要求找到数组中独步天下的k-diff没有错数码。 这里k-diff对被定义为整数对,当中i和j都以数组中的数字,它们的相对差是k。譬如:

输入:[3,1,4,1,5],k = 2输出:2表达:数组中有五个2-diff对,和。即使我们在输入中有七个1,但我们应该只回去唯大器晚成没错多少。

输入:[1,2,3,4,5],k = 1出口:4认证:数组中有多个1-diff对,,,和。

输入:[1,3,1,5,4],k = 0输出:1验证:数组中有一个0-diff对,。

注意:

  • 对和计为同风华正茂对。

  • 数组的长度不会超越10,000。

  • 给定输入中的全数整数都归属以下范围:[-1e7, 1e7]。

此次解题使用的开垦工具是eclipse,jdk使用的版本是1.8,境遇是win7 60人系统,使用Java语言编写和测量试验。

03 第二种解法

首先种解法时间复杂度太高了,得裁减点。第后生可畏种解法,大家是做减法,求相对值,来剖断是不是等于k,大家也足以做加法,拿当前成分加上k,然后看新因素是还是不是存在于数组中。同期还要思忖重新的计量数据,因而踏香港足球总会括的元素是唯豆蔻梢头的,对此大家得以接纳HashMap,已成分值作为key,该成分值现身次数为value。遍历key,假设key加上k后的值存在于map中,次数加1,别的倘若k为0的时候,只供给判别每种key所对应的value是还是不是高于等于2就可以。

此解法的时间复杂度是O,最坏处境也或者是O,空间复杂度是O。

public int findPairs2(int[] nums, int k) { if (nums == null || nums.length == 0 || k < 0) { return 0; } Map<Integer,Integer> map = new HashMap<Integer,Integer>(); for (int n : nums) { map.put(n, map.getOrDefault; } int count = 0; if  { for (Integer key: map.keySet { if (map.get >= 2) { count  ; } } } else { for (Integer key: map.keySet { if (map.containsKey { count  ; } } } return count;}

本文由澳门新葡萄京娱乐网站发布于编程知识,转载请注明出处:【IT笔试面试题整理】数组中现身次数超过六分之

关键词: