网站设计与运营第二次,任县网站建设设计,骨科医院网站模板,dedecms资源下载模板1552. 两球之间的磁力
题目
在代号为 C-137 的地球上#xff0c;Rick 发现如果他将两个球放在他新发明的篮子里#xff0c;它们之间会形成特殊形式的磁力。Rick 有 n 个空的篮子#xff0c;第 i 个篮子的位置在 position[i] #xff0c;Morty 想把 m 个球放到这些篮子里Rick 发现如果他将两个球放在他新发明的篮子里它们之间会形成特殊形式的磁力。Rick 有 n 个空的篮子第 i 个篮子的位置在 position[i] Morty 想把 m 个球放到这些篮子里使得任意两球间 最小磁力 最大。
已知两个球如果分别位于 x 和 y 那么它们之间的磁力为 |x - y| 。
给你一个整数数组 position 和一个整数 m 请你返回最大化的最小磁力。 示例 1 输入position [1,2,3,4,7], m 3
输出3
解释将 3 个球分别放入位于 14 和 7 的三个篮子两球间的磁力分别为 [3, 3, 6]。最小磁力为 3 。我们没办法让最小磁力大于 3 。示例 2
输入position [5,4,3,2,1,1000000000], m 2
输出999999999
解释我们使用位于 1 和 1000000000 的篮子时最小磁力最大。提示
n position.length2 n 10^51 position[i] 10^9所有 position 中的整数 互不相同 。2 m position.length
思路 根据题目可以知道是从最小中找到最大答案越小越有可能越大可能越小所以答案是单调的所以这里采用二分答案算法 首先需要将数组有序化才能进行二分查找 二分答案算法需要一个check函数根据题目建立check函数这道题中最小的一定会选那么计数初始化为1遍历查找price数组中满足相邻差值大于mid的元素计数增加最后如果遍历完计数计数k代表有这个组合为真如果计数k则不满足为假二分查找如果满足check就放弃右半区间或左半区间如果不满足就放弃左半区间或右半区间。一直往复直至到最终的答案 代码 bool check(int* position, int positionSize, int m, int mid) {int count 1;int x0 position[0];for(int j 0;jpositionSize;j){if(position[j] x0mid){count;x0 position[j];}}return countm;
}
int cmp(const void* a,const void* b){return *(int*)a-*(int*)b;
}
int maxDistance(int* position, int positionSize, int m) {qsort(position,positionSize,sizeof(int),cmp);int low 1, high position[positionSize - 1];int ans 0;while (low high) {int mid (low high) / 2;if (check(position, positionSize, m, mid)) {ans mid;low mid 1;} else {high mid - 1;}}return ans;
} 1748. 唯一元素的和
题目
给你一个整数数组 nums 。数组中唯一元素是那些只出现 恰好一次 的元素。
请你返回 nums 中唯一元素的 和 。 示例 1
输入nums [1,2,3,2]
输出4
解释唯一元素为 [1,3] 和为 4 。示例 2
输入nums [1,1,1,1,1]
输出0
解释没有唯一元素和为 0 。示例 3
输入nums [1,2,3,4,5]
输出15
解释唯一元素为 [1,2,3,4,5] 和为 15 。提示
1 nums.length 1001 nums[i] 100
思路 这里运用哈希解决 先将数组映射到哈希中索引就是数组元素索引指向数组的值表示数组元素出现过几次然后遍历哈希中键值的位置如果为1代表着数组元素是唯一元素那么增加到总数当中。
代码
int sumOfUnique(int* nums, int numsSize) {int hash[101];memset(hash,0,sizeof(hash));for(int i 0 ;i numsSize ;i ){hash[nums[i]];}int sum 0;for(int i 0;inumsSize;i){if(hash[nums[i]] 1){sumnums[i];}}return sum;
}
