首页 > 分享一道字节面试算法题:统计数字出现的次数
头像
煎饼果子w
编辑于 2021-08-30 23:38
+ 关注

分享一道字节面试算法题:统计数字出现的次数

上次面试字节,碰到一个比较有意思的算法题,记录一下,给各位牛友分享。
题意:
给定一个无序数组,长度为n,每个元素都属于范围[1,n]之间,使用时间复杂度O(n)+空间复杂度O(1)的方法,求得每个元素的出现次数。
比如给定数组[1,2,2,3,5,3],最后的结果就是类似于1:1,2:2,3:2,5:1的形式,表示1出现了1次,2出现了2次,3出现了2次,5出现了1次。

解法:
这里限定了时间复杂度,那么只能用边遍历边替换的思路,力扣有移到类似的题 缺失的第一个正数,可以移步查看。

思想就是遍历数组,通过当前位置的数找到对应的下标位置,如果为正数,说明还没有被访问到,需要交换并置为-1,若为负数,需要减去1,若找到的下标不为自己,则把当前位置设为0,之后继续遍历。

步骤:

       1,2,2,3,5,3
第一步 -1,2,2,3,5,3
第二步 -1,-1,2,3,5,3
第三步 -1,-2,0,3,5,3
第四步 -1,-2,-1,0,5,3
第五步 -1,-2,-1,0,-1,3
第六步 -1,-2,-2,0,-1,0

代码:

public class Main {
    public static void main(String[] args) {
        int[][] nums = {
                {1, 1, 2, 2, 3, 5, 2, 3},
                {2, 3, 2, 3, 1},
                {5, 4, 3, 2, 1}
        };
        for (int[] num : nums) {
            System.out.println(Arrays.toString(count(num)));
        }
        // [-2, -3, -2, 0, -1, 0, 0, 0]
        // [-1, -2, -2, 0, 0]
        // [-1, -1, -1, -1, -1]
    }

    public static int[] count(int[] nums) {
        int n = nums.length;
        int i = 0;
        while (i < n) {
            // 只考虑大于0的元素
            while (nums[i] > 0) {
                // 下一个位置
                int next = nums[i] - 1;
                if (nums[next] > 0) {
                    // 交换元素
                    nums[i] = nums[next];
                    nums[next] = -1;
                } else {
                    nums[i] = 0;
                    nums[next]--;
                }
            }
            ++i;
        }
        return nums;
    }
}

全部评论

(5) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐