Java C++ 算法题解leetcode1608特殊数组特征值

目录
  • 题目要求
  • 思路一:枚举 + 二分
    • Java
    • C++
  • 思路二:二分枚举
    • Java
    • C++
  • 思路三:倒序枚举
    • Java
    • C++

题目要求

思路一:枚举 + 二分

  • 逐一枚举值域内的所有值,然后二分判断是否合法。

Java

class Solution {
    public int specialArray(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for (int x = 0; x <= nums[n - 1]; x++) { // 枚举
            int l = 0, r = n -1 ;
            while (l < r) { // 二分
                int m = l + r >> 1;
                if (nums[m] >= x)
                    r = m;
                else
                    l = m + 1;
            }
            if (nums[r] >= x && x == n - r)
                return x;
        }
        return -1;
    }
}
  • 时间复杂度:O(n log⁡ n),排序复杂度为O(n log⁡ n),枚举次数为值域范围C=1000,所以找答案的复杂度为O(C log n)
  • 空间复杂度:O(log⁡ n))

C++

class Solution {
public:
    int specialArray(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for (int x = 0; x <= nums[n - 1]; x++) { // 枚举
            int l = 0, r = n -1 ;
            while (l < r) { // 二分
                int m = (l + r) >> 1;
                if (nums[m] >= x)
                    r = m;
                else
                    l = m + 1;
            }
            if (nums[r] >= x && x == n - r)
                return x;
        }
        return -1;
    }
};
  • 时间复杂度:O(n log ⁡n),排序复杂度为O(n log⁡ n),枚举次数为值域范围C=1000,所以找答案的复杂度为O(C log⁡ n)
  • 空间复杂度:O(log⁡ n)

思路二:二分枚举

二分枚举+二分判定是否合法;

为了方便把判断合法单独写成函数getResgetResgetRes。

Java

class Solution {
    int[] nums;
    public int specialArray(int[] num) {
        this.nums = num;
        Arrays.sort(nums);
        int l = 0, r = nums[nums.length - 1];
        while (l < r) {
            int m = l + r >> 1;
            if (getRes(m) <= m)
                r = m;
            else
                l = m + 1;
        }
        return getRes(r) == r ? r : -1;
    }
    int getRes(int x) {
        int n = nums.length, l = 0, r = n - 1;
        while (l < r) {
            int m = l + r >> 1;
            if (nums[m] >= x)
                r = m;
            else
                l = m + 1;
        }
        return nums[r] >= x ? n - r : 0;
    }
}
  • 时间复杂度:O(n log⁡ n),排序复杂度为O(n log ⁡n),二分找答案所以复杂度为O(log ⁡C log ⁡n)
  • 空间复杂度:O(log ⁡n)

C++

  • 注意全局变量和输入变量需要有差别……
class Solution {
public:
    vector<int> nums;
    int specialArray(vector<int>& num) {
        this->nums = num;
        sort(nums.begin(), nums.end());
        int l = 0, r = nums[nums.size() - 1];
        while (l < r) {
            int m = (l + r) >> 1;
            if (getRes(m) <= m)
                r = m;
            else
                l = m + 1;
        }
        return getRes(r) == r ? r : -1;
    }
    int getRes(int x) {
        int n = nums.size(), l = 0, r = n - 1;
        while (l < r) {
            int m = (l + r) >> 1;
            if (nums[m] >= x)
                r = m;
            else
                l = m + 1;
        }
        return nums[r] >= x ? n - r : 0;
    }
};
  • 时间复杂度:O(n log⁡ n),排序复杂度为O(n log ⁡n),二分找答案所以复杂度为O(log⁡ C log⁡ n)
  • 空间复杂度:O(log⁡ n)

思路三:倒序枚举

  • 因为值域比较小,所以可以直接从值域最后开始倒着枚举;
  • 预处理出每个值出现的次数,然后记录当前合法合法数值的数量与当前数值进行比较。

Java

class Solution {
    public int specialArray(int[] nums) {
        int[] cnt = new int[1001];
        for (int x : nums)
            cnt[x]++;
        for (int i = 1000, tot = 0; i >= 0; i--) {
            tot += cnt[i]; // 数量
            if (i == tot)
                return i;
        }
        return -1;
    }
}
  • 时间复杂度:O(n+C)
  • 空间复杂度:O(C)

C++

class Solution {
public:
    int specialArray(vector<int>& nums) {
        int cnt[1001];
        memset(cnt, 0, sizeof(cnt));
        for (int x : nums)
            cnt[x]++;
        for (int i = 1000, tot = 0; i >= 0; i--) {
            tot += cnt[i];
            if (i == tot)
                return i;
        }
        return -1;
    }
};
  • 时间复杂度:O(n+C)
  • 空间复杂度:O(C)

以上就是Java C++ 算法题解leetcode1608特殊数组特征值的详细内容,更多关于Java C++ 算法特殊数组特征值的资料请关注我们其它相关文章!

(0)

相关推荐

  • Java C++ 算法题解leetcode652寻找重复子树

    目录 题目要求 思路一:DFS+序列化 Java C++ Rust 思路二:DFS+三元组 Java C++ Rust 总结 题目要求 思路一:DFS+序列化 设计一种规则将所有子树序列化,保证不同子树的序列化字符串不同,相同子树的序列化串相同. 用哈希表存所有的字符串,统计出现次数即可. 定义map中的关键字(key)为子树的序列化结果,值(value)为出现次数. 此处采用的方式是在DFS遍历顺序下的每个节点后添加"-",遇到空节点置当前位为空格. Java class Solut

  • Java C++算法题解leetcode1592重新排列单词间的空格

    目录 题目要求 思路:模拟 Java C++ Rust 题目要求 思路:模拟 模拟就完了 统计空格数量和单词数量,计算单词间应有的空格数,将它们依次放入结果字符串,若有余数则在末尾进行填补. Java class Solution { public String reorderSpaces(String text) { int n = text.length(), spcnt = 0; List<String> words = new ArrayList<>(); for (int

  • Java C++ 算法题解leetcode145商品折扣后最终价格单调栈

    目录 题目要求 思路一:暴力模拟 Java C++ Rust 思路二:单调栈 Java C++ Rust 题目要求 思路一:暴力模拟 由于数据范围不算离谱,所以直接遍历解决可行. Java class Solution { public int[] finalPrices(int[] prices) { int n = prices.length; int[] res = new int[n]; for (int i = 0; i < n; i++) { int discount = 0; fo

  • Java C++ 算法题解leetcode669修剪二叉搜索树示例

    目录 题目要求 思路一:模拟迭代 Java C++ 思路二:递归 Java C++ Rust 题目要求 思路一:模拟迭代 依次判断每个节点是否合法: 首先找出结果的根,若原根小了就拉右边的过来,大了拉左边的过来做新根: 然后分别判断左右子树的大小,由于二叉搜索树的性质,子树只需要判断一边就好: 左子树判断是否>low,合法就向左下走,不合法往右下: 右子树判断是否<high,合法就向右下走,不合法往左下. Java class Solution { public TreeNode trimBS

  • Java C++ 算法题解leetcode1582二进制矩阵特殊位置

    目录 题目要求 思路:模拟 Java C++ Rust 题目要求 思路:模拟 直接按题意模拟,先算出每行每列中“111”的个数,然后判断统计行列值均为111的位置即可. Java class Solution { public int numSpecial(int[][] mat) { int n = mat.length, m = mat[0].length; int res = 0; int[] row = new int[n], col = new int[m]; for (int i =

  • Java C++ 算法leetcode828统计子串中唯一字符乘法原理

    目录 题目要求 思路:模拟 java C++ Rust 题目要求 思路:模拟 解题的核心思想在于逆向思维,不考虑每个子数组中的唯一字符个数,转而考虑每个字符可以作为多少个子数组的唯一字符: 所以在计算答案时的算式和示例中给出的是不一样的: 在计算每个字符“贡献”[即当前向左向右分别可组成的答案个数]的时候要用到乘法原理. 对每一个字符s[i]s[i]s[i]都记录其左边和右边的第一个相同字符位置,分别记为l[i]l[i]l[i]和r[i]r[i]r[i],这两个位置中间构成的就是s[i]s[i]

  • Java C++ 算法题解leetcode1608特殊数组特征值

    目录 题目要求 思路一:枚举 + 二分 Java C++ 思路二:二分枚举 Java C++ 思路三:倒序枚举 Java C++ 题目要求 思路一:枚举 + 二分 逐一枚举值域内的所有值,然后二分判断是否合法. Java class Solution { public int specialArray(int[] nums) { Arrays.sort(nums); int n = nums.length; for (int x = 0; x <= nums[n - 1]; x++) { //

  • Java C++算法题解leetcode801使序列递增的最小交换次数

    目录 题目要求 思路:状态机DP 实现一:状态机 Java C++ Rust 实现二:滚动数组 Java C++ Rust 总结 题目要求 思路:状态机DP 实现一:状态机 Java class Solution { public int minSwap(int[] nums1, int[] nums2) { int n = nums1.length; int[][] f = new int[n][2]; for (int i = 1; i < n; i++) f[i][0] = f[i][1]

  • java算法题解牛客BM99顺时针旋转矩阵示例

    目录 题目描述 解题思路 实践代码 解法1 解法2 题目描述 BM99 顺时针旋转矩阵 描述 有一个NxN整数矩阵,请编写一个算法,将矩阵顺时针旋转90度. 给定一个NxN的矩阵,和矩阵的阶数N,请返回旋转后的NxN矩阵. 数据范围:0<n<300,矩阵中的值满足0≤val≤1000 要求:空间复杂度 O(N^2),时间复杂度 O(N^2) 进阶:空间复杂度 O(1),时间复杂度 O(N^2) 示例1输入:[[1,2,3],[4,5,6],[7,8,9]],3返回值:[[7,4,1],[8,5

  • java算法题解Leetcode15三数之和实例

    目录 题目 解题思路 题目 15. 三数之和 给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组. 注意:答案中不可以包含重复的三元组. 示例 1:输入:nums = [-1,0,1,2,-1,-4]输出:[[-1,-1,2],[-1,0,1]]示例 2:输入:nums = []输出:[]示例 3:输入:nums = [0]输出:[]提示:0 <= nums.length <=

  • 剑指Offer之Java算法习题精讲数组与字符和等差数列

    题目一  解法 class Solution { public int[] relativeSortArray(int[] arr1, int[] arr2) { int[] arr = new int[1001]; int[] ans = new int[arr1.length]; int index = 0; for(int i =0;i<arr1.length;i++){ arr[arr1[i]]+=1; } for(int i = 0;i<arr2.length;i++){ while

  • 剑指Offer之Java算法习题精讲数组与列表的查找及字符串转换

    题目一 解法 class Solution { public String toLowerCase(String s) { StringBuilder sb = new StringBuilder(); for(int i = 0;i<s.length();i++){ char ch = s.charAt(i); if('A'<=ch&&ch<='Z'){ ch = (char)(ch+32); } sb.append(ch); } return sb.toString(

随机推荐