I recently came across a Microsoft Interview Question for Software Engineer.
Given an array of positive and negative integers, re-arrange it so that you have positive integers on one end and negative integers on other, but retain their order of appearance in the original array.
For example, given [1, 7, -5, 9, -12, 15]
[-5, -12, 1, 7, 9, 15]
This should be done in O(n) time complexity and O(1) space complexity.
We could easily do it in O(n) time complexity, but I am not able to think how we can maintain the order of elements as in original array. If we forget about O(n) complexity, could someone tell me how we can preserve the order of elements without taking into consideration the s开发者_开发知识库pace- and time-complexity.
To achieve this result in constant space (but quadratic time), you can use the two-queue approach by placing one queue at each end of the array (similar to the Dutch National Flag algorithm). Read items left-to-right : adding an item to the left queue means leaving it alone, adding an item to the right queue means shifting all elements not in a queue to the left by one and placing the added item at the end. Then, to concatenate the queues, simply reverse the order of elements in the second queue.
This performs an O(n) operation (shifting elements left) up to O(n) times, which yields an O(n²) running time.
By using a method similar to merge sort, you can achieve a lower O(n log n) complexity: slice the array in two halves, recursively sort them in the form [N P] [N P] then swap the first P with the second N in O(n) time (it gets a bit tricky when they don't have exactly the same size, but it's still linear).
I have absolutely no idea of how to get this down to O(n) time.
EDIT: actually, your linked list insight is right. If the data is provided as a doubly linked list, you can implement the two-queue strategy in O(n) time, O(1) space:
sort(list):
negative = empty
positive = empty
while (list != empty)
first = pop(list)
if (first > 0)
append(positive,first)
else
append(negative,first)
return concatenate(negative,positive)
With a linked list implementation that keeps pointers to the first and last elements, then pop, append and concatenate are all O(1) operations, so the total complexity is O(n). As for space, none of the operations allocate any memory (append merely uses the memory released by pop), so it's O(1) overall.
Here is a constriant version of O(n) time O(1) space solution, it assume maxValue*(maxValue+1) is less than Integer.MAX_VALUE, where maxValue is the result of maxmum value minus minmum value in the array. It utilize the original array as the temporary array to store the result.
public static void specialSort(int[] A){
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
for(int i=0; i<A.length; i++){
if(A[i] > max)
max = A[i];
if(A[i] < min)
min = A[i];
}
//Change all values to Positive
for(int i=0; i<A.length; i++)
A[i]-= min;
int newMax = max-min+1;
//Save original negative values into new positions
int currNegativeIndex = 0;
for(int i=0; i<A.length; i++)
if(A[i]%newMax < (-min))
A[currNegativeIndex++] += (A[i]%newMax)*newMax;
//Save original positive values into new positions
int currPositiveIndex = currNegativeIndex;
for(int i=0; i<A.length; i++)
if(A[i]%newMax > (-min))
A[currPositiveIndex++] += (A[i]%newMax)*newMax;
//Recover to original value
for(int i=0; i<A.length; i++){
A[i] = A[i]/newMax + min;
}
}
I'm not sure I understand the question correctly, as the answer appears to be too simple:
- Walk through the array and count negative numbers - O(n)
- Create a new array of size O(n)
- Walk through original array and place numbers into the new array. Use the known number of negative numbers to offset the positive ones - O(n)
Here's a quick way to do it in Python. It slightly differs from the above in first creating an array for the negatives, then appending the positives. So it's not as efficient, but still O(n).
>>> a = [1,7,-5,9,-12,15]
>>> print [x for x in a if x < 0] + [y for y in a if y >= 0]
[-5, -12, 1, 7, 9, 15]
Edit: Ok, now with O(1) space compexity it gets much harder. I'm interested in how to achieve it in O(n) time complexity, too. If it helps, here's a way to keep the O(1) space complexity, but requires O(n^2) time complexity:
- Start from the leftmost negative number. Walk through the array until you find the next negative number.
- In a new loop, exchange the negative number with the positive number left of it. Do this until you reach the other negative numbers. This ensures the order of the numbers remains unchanged.
- Rince and repeat until you reach the end of the array when looking for a new negative number.
It can be done in O(n) and space O(1).
We need to scan 3 times through the array and change some values carefully.
Assumption: the max value in the array with size N is should be smaller than (N+1) * Integer.MAX_VALUE.
We need this assumption since we well change some positive values in the array.
- In the first scan, find # of negative and positive values, and the max.
- In the second scan we create the negative section of array as follows:
We start from the beginning of the array and we "swap" the first found positive number (e.g. at index i) with the first found negative number (e.g. j). Since negative numbers are being considered with respect to their location, the swap will be okay.
The problem is the positive numbers because there might be some other positive numbers between i and j. To handle this issue, we have to somehow encode the index of the positive number in that value before swapping. So then we can realize where it was at the first point. We can do this by a[i]=(i+1)*(max)+a[i].
- In the third scan, we create the positive section of array. by end of the second scan, the negative array is constructed, and the positive numbers are shifted to the right side, but their location may not be correct. So we go though it and correct their position since this info was encoded their value.
Here is the code:
import java.util.Arrays;
public class LinearShifting {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = {-1,7,3,-5,4,-3,1,2};
sort(a);
System.out.println(Arrays.toString(a)); //output: [-1, -5, -3, 7, 3, 4, 1, 2]
}
public static void sort(int[] a){
int pos = 0;
int neg = 0;
int i,j;
int max = Integer.MIN_VALUE;
for(i=0; i<a.length; i++){
if(a[i]<0) neg++;
else pos++;
if(a[i]>max) max = a[i];
}
max++;
if(neg==0 || pos == 0) return;//already sorted
i=0;
j=1;
while(true){
while(i<=neg && a[i]<0) i++;
while(j<a.length && a[j]>=0) j++;
if(i>neg || j>=a.length) break;
a[i]+= max*(i+1);
swap(a,i,j);
}
i = a.length-1;
while(i>=neg){
int div = a[i]/max;
if(div == 0) i--;
else{
a[i]%=max;
swap(a,i,neg+div-2);// minus 2 since a[i]+= max*(i+1);
}
}
}
private static void swap(int[] a, int i , int j){
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
Edit (5/29/2015): I overlooked the requirement for maintaining order of appearance, so the answer below does not satisfy all of the requirements of the question. However, I leave the original response up for general interest.
This is a special version of a very important subroutine of quicksort known as "partition." Definition: an array A having N numeric entries is partitioned about value K at index p if A[i] < K for 0 <= i < p and A[j] >= K for p <= j < N, unless all the entries are less than K (meaning p = N) or not less than K (meaning p = 0). For the problem in question, we will partition the array around K = 0.
You can partition an unsorted array about any value K in O(n) time, accessing each entry in the array just once, using O(1) additional memory. Informally, you step through the array from both ends, moving values that are on the wrong side. Perform a swap when one misplaced value is found on each side of the array, then continuing stepping inward. Now the C++ code:
// Assume array A[] has size N
int K = 0; // For particular example partitioning positive and negative numbers
int i = 0, j = N-1; // position markers, start at first and last entries
while(1) { // Break condition inside loop
while(i < N && A[i] < K) i++; // Increase i until A[i] >= K
while(j >= 0 && A[j] >= K) j--; // Decrease j until A[j] < K
if(i < j)
swap(A[i],A[j]);
else
break;
}
// A[] is now partitioned, A[0]...A[j] < K, unless i==0 (meaning all entries >= K).
Note that if all elements are equal to K (zero in this case), i is never incremented and j = 0 at the end. The problem statement assumes this will never happen. Partition is very fast and efficient, and this efficiency is the reason why quicksort is the most popular sorting routine for large arrays. The swap function can be std::swap in C++ or you can easily write your own:
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
Or just for fun, numbers can be swapped in place with no temporary memory, though be mindful of overflow:
// This code swaps a and b with no extra space. Watch out for overflow!
a -= b;
b += a;
a = b - a;
There are many variations to partition for special cases, such as a three way partition for [elements < K] [elements == K] [elements > K]. The quicksort algorithm calls partition recursively, and the partition value K is usually the first entry in the current sub-array or computed from a few entries (such as median of three). See textbooks: Algorithms by Sedgewick and Wayne (4th ed., p. 288) or The Art of Computer Programming Vol. 3 by Knuth (2nd ed., p. 113).
This solution has O(n) time complexity and O(1) space complexity
Idea is:
keep track of index of last seen negative element (lastNegIndex).
loop through the array to find negative elements that are preceded by positive element.
If such element is found, right rotate elements between lastNegIndex and current Index by one. Then update lastNegIndex (it will be next index).
Here is the code:
public void rightRotate(int[] a, int n, int currentIndex, int lastNegIndex){
int temp = a[currentIndex];
for(int i = currentIndex; i > lastNegIndex+ 1; i--){
a[i] = a[i-1];
}
a[lastNegIndex+1] = temp;
}
public void ReArrange(int[] a, int n){
int lastNegIndex= -1;
int index;
if(a[0] < 0)
lastNegIndex = 0;
for(index = 1; index < n; index++){
if (a[index] < 0 && a[index - 1] >= 0) {
rightRotate(a, n, index, lastNegIndex);
lastNegIndex = lastNegIndex + 1;
}
}
}
You can use 2 queues and merge them. That way, you only iterate once on the first array and once each sub queue.
negatives = []
positives = []
for elem in array:
if elem >= 0:
positives.push(elem)
else
negatives.push(elem)
result = array(negatives, positives)
Here's a solution with only 2 iterations:
Let's say the length is n.
And i'll use C like code, ignore syntax errors.
solution[n];
for (i= 0,j=0 ; i < n ; i++ ) {
if (array[i] < 0) solution[j++] = array[i];
}
for (i = n-1,j=n-1 ; ; i > 0 ; i--) {
if (array[i] >= 0) solution[j--] = array[i];
}
The idea is to go over it once, and write all the negatives we encounter.
Then go over it the second time from the end, and write the positives from the end towards the beginning.
If the structure in the beginning doesn't have to be an array, it's even simpler.
If you have the original numbers in a linked list it's easy.
You can re-arrange the linked list, just each time point the negative's next to the next negative, and the positive's next to the next positive.
Again C like code, ignore syntax. (might need a null check here and there, but this is the idea)
Cell firstPositive;
Cell* lastPoisitive;
lastPoisitive = &firstPositive;
Cell firstNegative;
Cell* lastNegative;
lastNegative = &firstNegative;
Cell* iterator;
for(Iterator = list.first ; Iterator != null ; Iterator = Iterator->next) {
if (Iterator->value > 0 ) lastPoisitive->next = Iterator;
else lastPoisitive->next = Iterator;
}
list.first = firstNegative->next;
list.last.next = firstPositive->next;
Just an idea.. Let's consider a simplier problem:
Given an array, where first part (Np elements) contains only positive numbers, and last part (Nn elements): only negative ones.
How to swap these parts while mainaning the relative order?
Simpliest solution is to use inversion:
inverse(array, Np + Nn); // whole array
inverse(array, Nn); // first part
inverse(array+Nn, Np); // second part
It has O(n) time complexity and O(1) space complexity.
If the goal is O(1) space (besides the elements themselves, which are assumed to be freely mutable) and O(NlgN) time, divide the problem into that of arranging arrays that are known to be of the form pnPN, where p and P represents zero or more positive numbers and n and N represents 0 or more negative numbers, into arrays of the form pPnN. Any two-element array will automatically be of that form. Given two arrays of that form, locate the first negative number, next positive number, and last positive number, and "spin" the middle two sections of the array (easy to do in constant space, and time proportional to the size of the array to be 'spun'). The result will be an array of the form pPnN. Two consecutive such arrays will form a larger array of the form pnPN.
To do things in constant space, start by pairing up all elements and putting them into PN form. Then do all quartets of elements, then all octets, etc. up to the total size of the array.
I very much doubt if O(n) time and O(1) is feasible with an array. Some suggest linked list, but you will need a custom linked list where you have direct access to the nodes to do this, ie. language-built-in linked lists won't work.
Here's my idea using a custom doubly linked list which satisfy the constrained complexities, using [1, 7, -5, 9, -12, 15] as an example:
Loop through the list, if see a negative, cut it off and add it to the end of the negatives at the front. Each operation is O(1) so total time is O(n). Linked list operations are in-place so O(1) space.
In detail:
last_negative_node = null;
at -5:
cut off -5 by setting 7.next = 9,
then add -5 to front by -5.next = 1,
then update last_negative_node = 5 // O(1), the linked list is now [-5, 1, 7, 9, -12, 15]
at -12:
cut off -12 by setting 9.next = 15,
then add -12 to front by -12.next = last_negative_node.next,
then update last_negative_node.next = -12,
then update last_negative_node = -12 //O(1), the linked list is now [-5, -12, 1, 7, 9, 15]
no more negatives so done.
O(n) solution Java
private static void rearrange(int[] arr) {
int pos=0,end_pos=-1;
for (int i=0;i<=arr.length-1;i++){
end_pos=i;
if (arr[i] <=0){
int temp_ptr=end_pos-1;
while(end_pos>pos){
int temp = arr[end_pos];
arr[end_pos]=arr[temp_ptr];
arr[temp_ptr]=temp;
end_pos--;
temp_ptr--;
}
pos++;
}
}
Here is a JavaScript implementation of qiwangcs's solution:
function specialSort(A){
let min = Number.MAX_SAFE_INTEGER, max = -Number.MAX_SAFE_INTEGER;
for(let i=0; i<A.length; i++){
if(A[i] > max)
max = A[i];
if(A[i] < min)
min = A[i];
}
//Change all values to Positive
for(let i=0; i<A.length; i++)
A[i]-= min;
const newMax = max-min+1;
//Save original negative values into new positions
let currNegativeIndex = 0;
for(let i=0; i<A.length; i++)
if(A[i]%newMax < (-min))
A[currNegativeIndex++] += (A[i]%newMax)*newMax;
//Save original positive values into new positions
let currPositiveIndex = currNegativeIndex;
for(let i=0; i<A.length; i++)
if(A[i]%newMax > (-min))
A[currPositiveIndex++] += (A[i]%newMax)*newMax;
//Recover to original value
for(let i=0; i<A.length; i++){
A[i] = Math.floor(A[i]/newMax) + min;
}
}
// Demo
const A = [-3,-7,2,8,-5,-2,4];
specialSort(A);
console.log(A);I think this would work: Here's a simple way that's constant space (but quadratic time). Say the array is length N. Walk along the array from i = 0 to i = N-2 checking element i and i+1. If element i is positive and element i+1 is negative, swap them. Then repeat that process.
Each pass across the array will make the negatives drift to the left (and positives drift to the right), sort of like a bubble sort, until (after sufficient number of passes) they are all in their correct place.
Also, I think this would work: It's also constant space (but quadratic time). Say P is the number of positives. Scan from left to right, when you find a positive x stop the scan, and "delete it" by shifting all the items after it left by one. Then put x at the end of the array. Repeat procedure scan P times to move every positive.
First, count the number k of negative elements.
Then, you know that the first k numbers of the array (first part of the array) should be negative.
The following N - k elements should be positive after sorting the array.
You maintain two counters of how many elements respect those conditions in both parts of the array and increment it at each step until you know that one part is OK (counter is equal to the size of that part). Then the other part is OK too.
This requires O(1) storage and takes O(N) time.
Implementation in C++ :
#include <iostream>
#include <vector>
using namespace std;
void swap(vector<int>& L, int i, int j) {
int tmp = L[i];
L[i] = L[j];
L[j] = tmp;
}
void signSort(vector<int>& L) {
int cntNeg = 0, i = 0, j = 0;
for (vector<int>::iterator it = L.begin(); it < L.end(); ++it) {
if (*it < 0) ++cntNeg;
}
while (i < cntNeg && cntNeg + j < L.size()) {
if (L[i] >= 0) {
swap(L, i, cntNeg + j);
++j;
} else {
++i;
}
}
}
int main(int argc, char **argv) {
vector<int> L;
L.push_back(-1);
L.push_back(1);
L.push_back(3);
L.push_back(-2);
L.push_back(2);
signSort(L);
for (vector<int>::iterator it = L.begin(); it != L.end(); ++it) {
cout << *it << endl;
}
return 0;
}
This code Work with O(n) complexity and O(1) space. No need to declare another array.
#include <stdio.h>
int* sort(int arr[], int size)
{
int i;
int countNeg = 0;
int pos = 0;
int neg = 0;
for (i = 0; i < size; i++)
{
if (arr[i] < 0)
pos++;
}
while ((pos < (size-1)) || (neg < size-(pos-1)))
{
if ((arr[pos] < 0) && (arr[neg] > 0))
{
arr[pos] = arr[pos] + arr[neg];
arr[neg] = arr[pos] - arr[neg];
arr[pos] = arr[pos] - arr[neg];
pos++;
neg++;
continue;
}
if ((arr[pos] < 0) && (arr[neg] < 0))
{
neg++;
continue;
}
if ((arr[pos] > 0) && (arr[neg] > 0))
{
pos++;
continue;
}
if ((arr[pos] > 0) && (arr[neg] < 0))
{
pos++;
neg++;
continue;
}
}
return arr;
}
void main()
{
int arr[] = { 1, 7, -5, 9, -12, 15 };
int size = sizeof(arr) / sizeof(arr[0]);
sort(arr, size);
int i;
for (i = 0; i < size; i++)
{
printf("%d ,", arr[i]);
}
printf(" \n\n");
}
#include <iostream>
using namespace std;
void negativeFirst_advanced (int arr[ ], int size)
{
int count1 =0, count2 =0;
while(count2<size && count1<size)
{
if(arr[count1]>0 && arr[count2]<0)
{
int temp = arr[count1];
arr[count1] = arr[count2];
arr[count2] = temp;
}
if (arr[count1]<0)
count1++;
if (arr [count2]>0)
count2++;
}
}
int main()
{
int arr[6] = {1,7,-5,9,-12,15};
negativeFirst_advanced (arr, 6);
cout<<"[";
for (int i =0; i<6;i++)
cout<<arr[i]<<" , ";
cout<<"]";
system("pause");
return 0;
}
Here is my solution in Python, using recursion (I had an assignment like this, where the array should be sorted relatively to a number K. If You put K = 0, You've got Your solution, without retaining the order of appearance):
def kPart(s, k):
if len(s) == 1:
return s
else:
if s[0] > k:
return kPart(s[1:], k) + [s[0]]
else:
return [s[0]] + kPart(s[1:], k)
This is not Complexity O(1) but a simpler approach. Do comment
void divide (int *arr, int len) {
int positive_entry_seen = 0;
for (int j = 0; j < len ; j++) {
if (arr[j] >= 0 ) {
positive_entry_seen = 1;
} else if ((arr[j] < 0 ) && positive_entry_seen) {
int t = arr[j];
int c = j;
while ((c >= 1) && (arr[c-1] >= 0)) {
arr[c] = arr[c-1];
c--;
}
arr[c] = t;
}
}
}
An extremely simple solution is below but not in O(n). I changed the insertion sort algorithm a bit. Instead of checking if a number is greater or smaller, it checks if they are greater or less than zero.
int main() {
int arr[] = {1,-2,3,4,-5,1,-9,2};
int j,temp,size;
size = 8;
for (int i = 0; i <size ; i++){
j = i;
//Positive left, negative right
//To get opposite, change it to: (arr[j] < 0) && (arr[j-1] > 0)
while ((j > 0) && (arr[j] >0) && (arr[j-1] < 0)){
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
j--;
}
}
//Printing
for(int i=0;i<size;i++){
cout<<arr[i]<<" ";
}
return 0;
}
A simple and easy solution which works in O(n) time complexity.
int left = 0;
int right = arr.length - 1;
while (left < right) {
while (arr[left] >= 0) {
left++;
}
while (arr[right] < 0) {
right--;
}
if (left < right) {
ArrayUtility.swapInArray(arr, left, right);
}
ArrayUtility.printArray(arr);
This uses partition process of QuickSort. The time complexity of this solution is O(n2) and auxiliary space is O(1). This approach maintains the order of appearance and have not used any other data structure. This is in Ruby
def sortSeg(intArr)
intArr.each_with_index do |el, idx|
# if current element is pos do nothing if negative,
# shift positive elements of arr[0..i-1],
# to one position to their right */
if el < 0
jdx = idx - 1;
while (jdx >= 0 and intArr[jdx] > 0)
intArr[jdx + 1] = intArr[jdx];
jdx = jdx - 1;
end
# Insert negative element at its right position
intArr[jdx + 1] = el;
end
end
end
int [] input = {1, 7, -5, 9, -12, 15};
int [] output = new int [input.length];
int negativeIdx = 0;
int positiveIdx = input.length - 1;
for(int i = 0; i < input.length ; i++) {
if(input[i] < 0) {
output [negativeIdx++] = input[i];
} else {
output [positiveIdx--] = input[i];
}
}
System.out.println
(Arrays.toString(output));
Output:
[-5, -12, 15, 9, 7, 1]
This can simply be done by following steps in O(n), without using any extra space
int count = 0;
//data is the array/vector in sort container having given input.
if(data[0] < 0)
count++;
for(int i = 1; i < n; i++)
{
if(data[i] < 0)
{
int j = i;
while(j> count)
{
data[j-1] += data[j];
data[j] = (data[j-1]-data[j]);
data[j-1] -= data[j];
j--;
}
count++;
}
}
it's complete implementation can be found here https://gist.github.com/Shravan40/8659568
I have hard-coded the values of the array. However it will work any set of integers.
int[] n={2,-3,1,5,-10,-8};
int k=0;
for(int i=1;i<n.length;i++)
{
int temp=0;
if(n[i]<0)
{
temp=n[k];
n[k]=n[i];
n[i]=temp;
k++;
}
}
for(int j=0;j<n.length;j++)
{
System.out.println(n[j]);
}
I hope this helps. This one has Time Complexity O(n^2)
#include <stdio.h>
int main() {
int a[] = {-3, 2, -5, 9, -2, -8, 6, 8, -1, 6};
int length = (sizeof(a) / sizeof(int));
int i, j = 0;
printf("Size of array: %d\n", sizeof(a));
for (i = 0; i < length; i++) {
if (i % 2 == 0 && a[i] < 0) {
for (j = i + 1; j < length; j++) {
if (a[j] > 0) {
int t = a[i];
a[i] = a[j];
a[j] = t;
break;
}
}
} else if (i % 2 == 1 && a[i] > 0) {
for (j = i + 1; j < length; j++) {
if (a[j] < 0) {
int t = a[i];
a[i] = a[j];
a[j] = t;
break;
}
}
}
}
for (i = 0; i < length; i++) {
printf("Value at %d: %d\n", i, a[i]);
}
return 0;
}
EDIT 1 This relies on the fact that numbers greater than zero are always at an even index and numbers less than zero are always at odd index
EDIT 2 Improved the code a little
here my answer is two separate positive and negative values in single array it will help you
int[] singleArray= {300, -310, 320, 340, 350,
-330, 420, 370, -360, 390,
340, -430, 320, -463, 450};
public double[] getPositive_SingleArray() {
double minValue = 0;
double positiveValue=0;
int count=0;
for (int i = 0; i < singleArrayData.length; i++) {
if ( singleArrayData[i]>0)
count++;
}
positiveSingleArrayData=new double[count];
int k=0;
for (int i = 0; i < singleArrayData.length; i++) {
if ( singleArrayData[i]>0){
positiveSingleArrayData[k] = singleArrayData[i];
k++;
}
}
System.out.println("single array of positve values "+Arrays.toString(positiveSingleArrayData));
return positiveSingleArrayData;
}
I've tried with the bubble sorting method and it works perfectly and it retain their order of appearance in the original array.
int main()
{
int array[TAM], num, i=0, j=0;
printf("Ingrese arreglo: ");
for(i=0; i < TAM -1 && num != 0; i++)
{
scanf("%d", &num);
array[i]=num;
}
for(i=0; array[i] != 0 ; i++)
{
j++;
}
Alternar(array, j);
//MOSTRAR
for(i=0; i < j; i++)
{
printf("%d ", array[i]);
}
return 0;
}
void Alternar(int array[], int j)
{
int i=0, aux, pasadas=1;
for(pasadas=1; pasadas < j; pasadas++)
{
for(i=0; i < j - pasadas ; i++)
{
if(array[i] > 0 && array[i+1] < 0)
{
aux = array[i];
array[i] = array[i+1];
array[i+1] = aux;
}
}
}
}Look at Heapsort in the table of sorting algorithms on Wikipedia: http://en.wikipedia.org/wiki/Sorting_algorithm
![Interactive visualization of a graph in python [closed]](https://www.devze.com/res/2023/04-10/09/92d32fe8c0d22fb96bd6f6e8b7d1f457.gif)
加载中,请稍侯......
精彩评论