经销做网站都有什么好处,如何做淘宝客个人网站,郑州治疗精神病哪家好,柯桥做网站哪家好题目一#xff1a; 剑指 Offer 03. 数组中重复的数字 找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0#xff5e;n-1 的范围内。数组中某些数字是重复的#xff0c;但不知道有几个数字重复了#xff0c;也不知道每个数字重复了几次。请找出数组中任…题目一 剑指 Offer 03. 数组中重复的数字 找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0n-1 的范围内。数组中某些数字是重复的但不知道有几个数字重复了也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1
输入
[2, 3, 1, 0, 2, 5, 3]
输出2 或 3
https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/ 解法一简单排个序遍历下做个对比
public int findRepeatNumber(int[] nums) {Arrays.sort(nums);for (int i 1; i nums.length; i) {if (nums[i]nums[i-1])return nums[i];}return -1;}
解法二用HashSet去重求解
public int findRepeatNumber1(int[] nums) {SetInteger set new HashSet();for (int i 0; i nums.length; i) {if (!set.add(nums[i]))return nums[i];}return 0;}
题目二
剑指 Offer 53 - I. 在排序数组中查找数字 I 统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums [5,7,7,8,8,10], target 8
输出: 2
示例 2:
输入: nums [5,7,7,8,8,10], target 6
输出: 0
https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/ 解法一最简单的遍历求解
public int search(int[] nums, int target) {int count 0;for (int num : nums) {if (num target) count;}return count;}
解法二 面试的话还是得二分查找加分解
public int search2(int[] nums, int target) {return helper(nums,target)-helper(nums,target-1);}private int helper(int[] nums, int target) {int low 0, high nums.length-1;while (low high){int mid low ((high-low)1);if (nums[mid]target){low mid 1;}else {high mid - 1;}}return low;}
题目三
剑指 Offer 53 - II. 0n-1中缺失的数字 一个长度为n-1的递增排序数组中的所有数字都是唯一的并且每个数字都在范围0n-1之内。
在范围0n-1内的n个数字中有且只有一个数字不在该数组中请找出这个数字。
示例 1:
输入: [0,1,3]
输出: 2
示例 2:
输入: [0,1,2,3,4,5,6,7,9]
输出: 8
https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/ 解法一暴力解法直接遍历判断
public int missingNumber(int[] nums) {for (int i 0; i nums.length; i) {if (nums[i]!i)return i;}return nums[nums.length-1]1;}
解法二二分查找套公式用一下位运算可以当抖个机灵 public int missingNumber1(int[] nums) {int low 0, high nums.length-1;while (lowhigh){int mid low ((high-low)1);if (nums[mid]mid) low mid 1;else high mid - 1;}return low;}
解法三数据结构解法标答用解法二和三都可以让人知道你会用算法和结构解决问题 public int missingNumber2(int[] nums) {int len nums.length;SetInteger set Collections.synchronizedSet(new HashSet());for (int i : nums) {set.add(i);}for (int i0;ilen;i){if (set.add(i)){return i;}}return 0;}
