求这道亚麻oa最优解

I don't remember the exact wording but. Given an array of integers, and a maximum difference k, return the minimum number of groups that any two integers do not have difference bigger than k.

Say, we have [6,1,3,4,3,5], and k is 2, we will return 2 because we have minimum of two groups [1,3,3] and [4,5,6].
The way I solved it is that I sorted the array first and iterate through the array. Is there a more optimal solution for this one?

Sort (如果题目不要求顺序)  + 二分法猜答案, low 1 high arr.length -1

去重后排序，再分

排序是NLOGN, 应该可以用O(N) 解： 先遍历把所有数字加入set 并找出最大最小，再从最小的min开始遍历，看 min +0-k 是不是在set里面，如果在就group++，并且 往前移动min += k+1， 这是ON  的解法，不知道有没有edge case 过不了

zxyOFHA 发表于 2022-03-10 06:35:40
排序是NLOGN, 应该可以用O(N) 解： 先遍历把所有数字加入set 并找出最大最小，再从最小的min开始遍历，看 min +0-k 是不是在set里面，如果在就group++，并且 往前移动mi

这样好像不行吧，因为原数组可能有重复数字的

补充内容 (2022-03-13 03:21 +08:00):
应该是他每个数字之间可以差很多，可能前一个数是一，下一个数就变成一万了，我感觉只能排序

pjy434 发表于 2022-3-12 14:12
这样好像不行吧，因为原数组可能有重复数字的

补充内容 (2022-03-13 03:21 +08:00):

觉得对的话加个米吧

1. public static int minGroupON(int[] awards, int k){        
   
2.         Set<Integer> set = new HashSet<>();
   
3.         int min = Integer.MAX_VALUE;
   
4.         int max = Integer.MIN_VALUE;
   
5.         for(int award: awards){
   
6.             set.add(award);
   
7.             min = Math.min(award,min);
   
8.             max = Math.max(award,max);
   
9.         }
   
10.         int pointer = min;
    
11.         int count = 0;
    
12.         while(pointer<=max){
    
13.             for(int i=0;i<=k;i++){
    
14.                 if(set.contains(pointer+i)){
    
15.                     pointer+=i;
    
16.                     count++;
    
17.                     break;
    
18.                 }
    
19.             }
    
20.             pointer+=k+1;
    
21.         }
    
22.         return count;   
    
23.     }

复制代码

zxyOFHA 发表于 2022-03-12 13:38:50
觉得对的话加个米吧public static int minGroupON(int awards, int k){        
        Set<Integer> set = new Ha

这不是o（n）啊。。。而且算出来也不对。我觉得不用排序最快kn，就是对于每个hashset里的数字，往上查k个连续数字看是不是在hashset里