比较两个有序的集合,集合中的数据从大到小排列,找到集合中第一次出现不相同的数据
时间: 2024-03-03 11:49:06 浏览: 10
可以使用双指针的方法来比较两个有序集合中第一次出现不相同的数据。具体步骤如下:
1. 初始化指针i和j,分别指向集合A和集合B的起始位置。
2. 循环比较集合A和集合B中指针指向的元素,如果两个元素相等,则将指针i和j分别向后移动一位,继续比较下一对元素。
3. 如果两个元素不相等,则记录下当前元素值,并结束比较。
4. 如果其中一个集合已经比较完了,而另一个集合还有元素剩余,则将指针j(或i)向后移动,直到找到不小于当前元素的第一个元素,记录该元素值,并结束比较。
以下是示例Python代码实现:
```python
def find_first_different_value(A, B):
i, j = 0, 0
while i < len(A) and j < len(B):
if A[i] == B[j]:
i += 1
j += 1
else:
return A[i] if A[i] < B[j] else B[j]
if i == len(A):
return B[j]
else:
return A[i]
```
其中A和B分别是两个有序集合,函数返回第一个不相同的元素值。
相关问题
查找两个大小不同的有序的List集合,并且list集合中的数据从大到小排列,找到两个集合第一次出现不同数据的大小,java代码实现
以下是Java代码实现:
```java
public class FindFirstDifferentElement {
public static void main(String[] args) {
// 两个有序的List集合
List<Integer> list1 = Arrays.asList(10, 8, 6, 4, 2);
List<Integer> list2 = Arrays.asList(10, 8, 7, 4, 2, 1);
// 找到两个集合第一次出现不同数据的大小
int i = 0, j = 0;
while (i < list1.size() && j < list2.size()) {
if (list1.get(i) != list2.get(j)) {
System.out.println("第一次出现不同数据的大小:" + Math.max(list1.get(i), list2.get(j)));
break;
}
i++;
j++;
}
}
}
```
输出结果为:
```
第一次出现不同数据的大小:6
```
解释一下代码,首先我们定义了两个有序的List集合`list1`和`list2`,其中`list1`的大小为5,`list2`的大小为6。然后我们使用双指针的方式遍历这两个List集合,比较每一个元素的大小。如果发现两个元素不相等,我们就找到了第一次出现不同数据的大小,输出这个大小即可。如果两个List集合完全相等,那么程序不会输出任何内容。
二分查找两个有序的List集合,并且list集合中的数据从大到小排列,找到两个集合第一次出现不同数据的大小,java代码实现
以下是Java代码实现二分查找两个有序的List集合中第一次出现不同数据的大小:
```java
public static <T extends Comparable<? super T>> T binarySearchFirstDifferentValue(List<T> A, List<T> B) {
int left = 0, right = A.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
int cmp = A.get(mid).compareTo(B.get(mid));
if (cmp == 0) {
left = mid + 1;
} else if (cmp < 0) {
right = mid - 1;
} else {
left = mid + 1;
}
}
if (left == A.size()) {
return B.get(right);
} else {
return A.get(left).compareTo(B.get(left)) < 0 ? A.get(left) : B.get(left);
}
}
```
其中A和B分别是两个有序的List集合,函数返回第一个不相同的元素值。由于List集合中的元素类型必须实现Comparable接口,因此我们可以使用T extends Comparable<? super T>来表示泛型类型T必须实现Comparable接口。在比较两个元素大小时,我们使用compareTo方法,它会返回一个整数,表示两个元素的大小关系。如果返回值为0,则说明两个元素相等;如果返回值小于0,则说明A[mid]小于B[mid];如果返回值大于0,则说明A[mid]大于B[mid]。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)