教学互动网站的设计,仿淘宝网站源码+php,巴中学校网站建设,怎么将公司网站设成首页数组能形成多少数对【LC2341】 给你一个下标从 0 开始的整数数组 nums 。在一步操作中#xff0c;你可以执行以下步骤#xff1a; 从 nums 选出 两个 相等的 整数从 nums 中 移除这两个整数#xff0c;形成一个 数对 请你在 nums 上多次执行此操作直到无法继续执行。 返回一…数组能形成多少数对【LC2341】 给你一个下标从 0 开始的整数数组 nums 。在一步操作中你可以执行以下步骤 从 nums 选出 两个 相等的 整数从 nums 中 移除这两个整数形成一个 数对 请你在 nums 上多次执行此操作直到无法继续执行。 返回一个下标从 0 开始、长度为 2 的整数数组 answer 作为答案其中 answer[0] 是形成的数对数目answer[1] 是对 nums 尽可能执行上述操作后剩下的整数数目。 哈希表 思路使用哈希表记录某个数字在这之前是否存在然后遍历每一个数字如果存在那么可以从nums中移除这两个整数形成一个 数对如果不存在那么将哈希表赋值为true。那么剩下的数字为数组长度-2*数对数目 实现 class Solution {public int[] numberOfPairs(int[] nums) {int n nums.length;boolean[] flag new boolean[101];int[] res new int[2];for (int num : nums){if (flag[num]){res[0];flag[num] false;}else{flag[num] true;}}res[1] n - 2 * res[0];return res;}
}复杂度 时间复杂度O(n)O(n)O(n)n为数组长度空间复杂度O(C)O(C)O(C)C为字符集大小本题中为101
排序 思路将数组排序从数组第一个元素开始遍历如果nums[i]nums[i1]那么可以形成一个数对指针向后移动两个否则后移一位 实现 class Solution {public int[] numberOfPairs(int[] nums) {int n nums.length;int[] res new int[2];Arrays.sort(nums);int i 0;while (i n - 1){if (nums[i] nums[i 1]){res[0];i 2;}else{i;}}res[1] n - 2 * res[0];return res;}
}复杂度 时间复杂度O(nlogn)O(nlogn)O(nlogn)n为数组长度空间复杂度O(1)O(1)O(1)
